我之前考试是遇到过这题，但是数据范围k<=20，状压就能过。
结果原题范围k<=100000……
果断线段树合并。
普及线段树合并：
比如两个相同大小的线段树,将b树各个区间上的值合并到a树上，从树根开始合并，然后递归合并左右儿子，有三种情况：
（假设现在a树遍历到x点，b树遍历到y点）
1.x，y至少其一未被修改过（语文不好勿喷），则将x变为遍历过的那个。
2.x，y位于叶节点（l==r），则sum[x]+=sum[y]。
3.一般情况，递归处理左右儿子，最后更新当前点。
本题中合并如下：
void merge(int &a,int b,int l,int r)
{ if(!b)return ; if(!a){a=b;return ;} //1 if(l==r){sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;}//注意维护 //2 int mid = (l+r)>>1;
merge(ls[a],ls[b],l,mid);//递归左子树
merge(rs[a],rs[b],mid+1,r);//递归右子树
update(a); //3
}juruo代码奉上：
#include<cstdio>#include<algorithm>using namespace std;#define N 100105inline int rd()
{ int f=1,c=0;char ch = getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();} return f*c;
}int n,m,hed[N],cnt;struct eg
{ int to; int nxt;
}e[2*N];void ae(int f,int t)
{
e[++cnt].to = t;
e[cnt].nxt = hed[f];
hed[f] = cnt;
}int dep[N],fa[N],son[N],tp[N],siz[N];void dfs1(int u)
{
dep[u]=dep[fa[u]]+1;
siz[u]=1; for(int j=hed[u];j;j=e[j].nxt)
{ int to = e[j].to; if(to==fa[u])continue;
fa[to]=u;
dfs1(to);
siz[u]+=siz[to]; if(siz[to]>siz[son[u]])son[u]=to;
}
}void dfs2(int u,int topn)
{
tp[u]=topn; if(!son[u])return ;
dfs2(son[u],topn); for(int j=hed[u];j;j=e[j].nxt)
{ int to = e[j].to; if(to==fa[u]||to==son[u])continue;
dfs2(to,to);
}
}int get_lca(int a,int b)
{ while(tp[a]!=tp[b])
{ if(dep[tp[a]]<dep[tp[b]])swap(a,b);
a=fa[tp[a]];
} return dep[a]<dep[b]?a:b;
}int rt[N],sum[70*N],sn[70*N],ls[70*N],rs[70*N],tot;void update(int u)
{
sn[u]=sum[ls[u]]>=sum[rs[u]]?sn[ls[u]]:sn[rs[u]];
sum[u]=sum[ls[u]]>=sum[rs[u]]?sum[ls[u]]:sum[rs[u]];
}void insert(int l,int r,int &u,int qx,int d)
{ if(!u)u=++tot; if(l==r)
{
sum[u]+=d; if(sum[u])sn[u]=l; else sn[u]=0; return ;
} int mid = (l+r)>>1; if(qx<=mid)insert(l,mid,ls[u],qx,d); else insert(mid+1,r,rs[u],qx,d);
update(u);
}void merge(int &a,int b,int l,int r)
{ if(!b)return ; if(!a){a=b;return ;} if(l==r){sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;} int mid = (l+r)>>1;
merge(ls[a],ls[b],l,mid);
merge(rs[a],rs[b],mid+1,r);
update(a);
}int ans[N];void dfs(int u)
{ for(int j=hed[u];j;j=e[j].nxt)
{ int to = e[j].to; if(to==fa[u])continue;
dfs(to);
merge(rt[u],rt[to],1,m);
}
ans[u]=sn[rt[u]];
}struct ND
{ int f,t,z;
}nd[N];bool cmp(ND a,ND b)
{ return a.z<b.z;
}int to[N];int main()
{
n=rd(),m=rd(); for(int f,t,i=1;i<n;i++)
{
f=rd(),t=rd();
ae(f,t),ae(t,f);
}
dfs1(1),dfs2(1,1); for(int f,t,z,i=1;i<=m;i++)
{
f=rd(),t=rd(),z=rd();
nd[i].f=f,nd[i].t=t,nd[i].z=z;
}
sort(nd+1,nd+1+m,cmp); int las=-1,k=0; for(int f,t,z,lca,i=1;i<=m;i++)
{ if(nd[i].z!=las)
{
las=nd[i].z;
to[++k]=nd[i].z;
}
nd[i].z=k;
f = nd[i].f,t = nd[i].t,z = nd[i].z;
lca = get_lca(f,t);
insert(1,m,rt[f],z,1);
insert(1,m,rt[t],z,1);
insert(1,m,rt[lca],z,-1); if(lca!=1)insert(1,m,rt[fa[lca]],z,-1);
}
dfs(1); for(int i=1;i<=n;i++)
{ printf("%d\n",to[ans[i]]);
} return 0;
}在这里提一下空间问题：
每进行一次插入，会添加log级的点，因此juruo认为开nlogn级数组即可。
原文出处：https://www.cnblogs.com/LiGuanlin1124/p/9571295.html