题目链接：
https://vjudge.net/contest/430000#problem/C
Solution：
题目保证有解，所以对于一组颜色相同的点，它们必定分布在一条树链上
所以求每一个颜色对应的两个端点，就是求一条能够包含这个颜色所有点的树链
我们不妨先dfs处理出每个点的深度，并对于每个颜色，记录出它深度最大和最小的点，分别记为(u_1)和(u_2)
显然最深的点一定可以作为这个颜色的一个端点
考虑某个颜色对应的链，分为两种情况，若这种颜色其他点都是(u_1)的祖先（也就是以(u_1)为起始沿着每个点的父亲一路向上的一条链，每个点与(u_1)的LCA都是他本身），那么(u_2)就是另一个端点；反之，若我们找到一类点，它不是(u_1)的祖先（该点与(u_1)的LCA不是他本身），那么，这类点中最深的点就是另一个端点
这一步我们可以用LCA来实现，这样一来，我们就处理出了每个颜色的两个端点了
下一步我们考虑安排颜色间的先后顺序，也就是每个颜色的拓扑序
由于一定有解，我们考虑，在某个颜色(C)对应的链上，若出现了另一个颜色(D)的点，显然，(D)一定在(C)后面（每个颜色只能画一次，(D)又出现在了(C)对应的链上，那么(D)肯定是把这个点之前的颜色(C)给覆盖了）,我们在拓扑图上把(C)和(D)连一条有向边即可
枚举每个颜色(C)，处理其对应的链，设(C)的两个端点为(c_1),(c_2),我们分别从(c_1,c_2)出发向上走到他们的LCA，遇到不是(C)的颜色在拓扑图上连边即可
这样对于每个颜色的连边是(O(n))的，我们可以用倍增优化
也就是当我们在(C)对应的链上遇到了另一种颜色(D)，我们直接倍增(log（n）)走完颜色(D)即可（若是颜色(C)就不要倍增跳了，因为可能会跳过链上的一些颜色导致遗漏，所以在颜色为(C)的点上还是老老实实往上跳吧，复杂度也不会炸，因为每个点你仅会用(O(n))的方式处理一次，遇到不属于颜色(C)的点再跳）
处理完所有颜色连好边后做个拓扑排序就行了
#include<bits/stdc++.h>
using namespace std;
struct front_star{
int to,next;
}e[200005];
int n,m,cnt=0,tot=0;
int col[100005],head[100005],f[100005][18],d[100005],tl[100005],hd[100005],tp[100005],deg[100005],ans[100005],p[100005];
set<int>s[100005];
vector<int>g[100005];
void addedge(int u,int v)
{
cnt++;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void get_deep(int u,int fa)
{
f[u][0]=fa;
for(int i=1;i<=17;i++)
f[u][i]=f[f[u][i-1]][i-1];
d[u]=d[fa]+1;
if(tl[col[u]]==0)
tl[col[u]]=u;
else
{
if(d[tl[col[u]]]<d[u])
tl[col[u]]=u;
}
if(tp[col[u]]==0)
tp[col[u]]=u;
else
{
if(d[tp[col[u]]]>d[u])
tp[col[u]]=u;
}
for(int i=head[u];~i;i=e[i].next)
{
if(e[i].to!=fa)
get_deep(e[i].to,u);
}
}
int get_lca(int x,int y)
{
if(d[x]<d[y])
swap(x,y);
for(int i=17;i>=0;i--)
{
if(d[x]-(1<<i)>=d[y])
x=f[x][i];
}
if(x==y)
return x;
for(int i=17;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
void jump(int u,int r,int des)
{
if(u==des)
return;
if(col[u]==r)
{
if(col[f[u][0]]!=r)
s[col[f[u][0]]].insert(r);
if(d[f[u][0]]>=d[des])
jump(f[u][0],r,des);
}
else
{
if(d[p[col[u]]]<d[des])
return;
if(col[u]!=col[f[u][0]])
{
if(col[f[u][0]]!=r)
s[col[f[u][0]]].insert(r);
if(d[f[u][0]]>=d[des])
jump(f[u][0],r,des);
}
else
{
for(int i=17;i>=0;i--)
{
if(col[f[u][i]]==col[u])
{
if(d[f[u][i]]<d[des])
return;
else
{
jump(f[u][i],r,des);
break;
}
}
}
}
}
}
void top_sort()
{
queue<int>q;
while(!q.empty()) q.pop();
for(int i=1;i<=m;i++)
{
if(deg[i]==0)
q.push(i);
}
while(!q.empty())
{
int t=q.front();
q.pop();
tot++;
ans[tot]=t;
int upp=g[t].size();
for(int i=0;i<upp;i++)
{
deg[g[t][i]]--;
if(deg[g[t][i]]==0)
q.push(g[t][i]);
}
}
}
int main()
{
memset(head,-1,sizeof(head));
memset(f,0,sizeof(f));
memset(tl,0,sizeof(tl));
memset(tp,0,sizeof(tp));
memset(hd,0,sizeof(hd));
memset(deg,0,sizeof(deg));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&col[i]);
for(int i=1;i<=m;i++)
{
s[i].clear();
g[i].clear();
}
for(int i=1;i<=n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
d[0]=0;
get_deep(1,0);
for(int i=1;i<=n;i++)
{
int c=col[i];
if(i!=tl[c]&&tl[c]!=0)
{
if(get_lca(i,tl[c])!=i&&d[i]>d[hd[c]])
hd[c]=i;
}
}
for(int i=1;i<=m;i++)
{
if(hd[i]==0)
hd[i]=tp[i];
p[i]=get_lca(hd[i],tl[i]);
}
for(int i=1;i<=m;i++)
{
if(hd[i]!=0&&tl[i]!=0)
{
int lca=get_lca(tl[i],hd[i]);
jump(tl[i],i,lca);
jump(hd[i],i,lca);
}
}
for(int i=1;i<=m;i++)
{
for(set<int>::iterator it=s[i].begin() ;it!=s[i].end();it++)
{
int c=*it;
g[c].push_back(i);
deg[i]++;
}
}
for(int i=1;i<=m;i++)
{
if(tl[i]==0||hd[i]==0)
printf("%d %d %d
",i,1,1);
}
top_sort();
for(int i=1;i<=m;i++)
{
if(hd[ans[i]]!=0&&tl[ans[i]]!=0)
printf("%d %d %d
",ans[i],tl[ans[i]],hd[ans[i]]);
}
return 0;
}