前置知识：lca , 树链剖分（最好会）

很显然，如果想让剖分次数最小，就让每一个节点的重儿子被访问的次数最多，所以我们就可以记录每一个点被访问的次数，可以用树上差分或真的用树链剖分来解决（这种方法我没试过)

我们每读入一次询问，就把 $siz[a]$ 和 $siz[b]$ 加 1，而因为树链刨分的时候只会访问到 $lca(a,b)$ ,我们就把 $siz[lca(a,b)]$ 减 1

但是如果在 $fa[a]/fa[b]=lca(a,b)$ 的情况下，那个节点是必须被访问一次的，所以我们就不需要再增加查封数组的值了，所以需要特判一下。

code:

#include<bits/stdc++.h>
using namespace std;
int n,q,head[100001],to[200001],nxt[200001],cnt,siz[100001],fa[100001][21],dep[100001],son[100001];
void add(int a,int b){
    nxt[++cnt]=head[a];
    head[a]=cnt;
    to[cnt]=b;
}
void dfs1(int now,int father,int deep){
    fa[now][0]=father;
    dep[now]=deep;
    for(int i=head[now];i;i=nxt[i]){
        if(to[i]==father)continue;
        dfs1(to[i],now,deep+1);
    } 
}
int lca(int a,int b){
    if(dep[a]>dep[b])swap(a,b);
    for(int i=20;i>=0;i--){
        if(dep[fa[b][i]]>=dep[a]){
            b=fa[b][i];
        }
    }
    if(a==b)return a;
    for(int i=20;i>=0;i--){
        if(fa[a][i]!=fa[b][i]){
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[b][0]; 
}
void dfs2(int now,int father){
    for(int i=head[now];i;i=nxt[i]){
        if(to[i]==father)continue;
        dfs2(to[i],now); 
        siz[now]+=siz[to[i]]; 
        if(siz[to[i]]>=siz[son[now]]){
            son[now]=to[i];
        } 
    }   
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs1(1,0,1);
    for(int l=1;l<=20;l++){
        for(int i=1;i<=n;i++){
            fa[i][l]=fa[fa[i][l-1]][l-1];
        }
    }
    for(int i=1;i<=q;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        int c=lca(a,b);
        if(fa[a][0]!=c){
            siz[a]++;
            siz[c]--;
        }
        if(fa[b][0]!=c){
            siz[b]++;
            siz[c]--;
        } 
    }
    dfs2(1,1);
    for(int i=1;i<=n;i++){
        printf("%d\n",son[i]);
    } 
    return 0;
}