题面：https://www.lydsy.com/JudgeOnline/problem.php?id=5457
题解：
线段树合并，对于每个节点维护sum（以该节点为根的子树中最大的种类和）和kind（以该节点为根的子树中种类和最大的种类）即可。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=(4e5)+;
int N,M,U,V,num_edge=,edge_head[maxn],root[maxn];
int num_treenode=;
struct Edge{int to,nx;}edge[maxn<<];
inline void Add_edge(int from,int to){
edge[++num_edge].nx=edge_head[from];
edge[num_edge].to=to;
edge_head[from]=num_edge;
return;
}
struct Tree{int lc,rc,l,r,sum,kd;}tr[maxn*];
inline void Pushup(int x){
int lc=tr[x].lc,rc=tr[x].rc;
if(tr[lc].sum>=tr[rc].sum){
tr[x].sum=tr[lc].sum;
tr[x].kd=tr[lc].kd;
}
else {
tr[x].sum=tr[rc].sum;
tr[x].kd=tr[rc].kd;
}
return;
}
inline void Build(int x,int l,int r,int q,int s){
tr[x].l=l;tr[x].r=r;int mid=(l+r)>>;
if(l==r&&l==q){
tr[x].kd=q;
tr[x].sum=s;
return;
}
if(q<=mid)Build(tr[x].lc=++num_treenode,l,mid,q,s);
else Build(tr[x].rc=++num_treenode,mid+,r,q,s);
Pushup(x);
return;
}
struct A_{int kd,sum;}A[maxn];
inline int Merge(int u,int v){
if(!u)return v;
if(!v)return u;
int l=tr[u].l,r=tr[u].r;
if(l==r){
tr[u].sum+=tr[v].sum;
return u;
}
tr[u].lc=Merge(tr[u].lc,tr[v].lc);
tr[u].rc=Merge(tr[u].rc,tr[v].rc);
Pushup(u);
return u;
}
inline void Dfs(int x,int fa){
for(int i=edge_head[x];i;i=edge[i].nx){
int y=edge[i].to;
if(y!=fa){
Dfs(y,x);
Merge(root[x],root[y]);
}
}
return;
}
int main(){
scanf("%d%d",&N,&M);
for(int i=;i<N;i++){
scanf("%d%d",&U,&V);
Add_edge(U,V);Add_edge(V,U);
}
for(int i=;i<=N;i++){
scanf("%d%d",&A[i].kd,&A[i].sum);
Build(root[i]=++num_treenode,,M,A[i].kd,A[i].sum);
}
Dfs(,);
for(int i=;i<=N;i++)printf("%d %d\n",tr[root[i]].kd,tr[root[i]].sum);
return ;
}
By:AlenaNuna