题面

有一棵树,根节点为1, 一共有 n n个节点,每个节点上都有一个口袋,我们称他们为树袋,现在计算鸭准备对这棵树进行 m m次操作, 第i次操作会给ai子树与bi子树的所有树袋都放进去一个编号为i的苹果,最后,对于每个树袋,计算出有多少其他的树袋与自己至少有一个编号一样的苹果.

样例

输入
11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8

输出
0 6 7 6 0 2 0 5 4 5 5 

std

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> VI;
typedef pair<int,int> PII;
#define rep(i,n) for(int i=0;i<n;i++)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn  =  100010;
VI edge[maxn],adj[maxn];
int L[maxn] , R[maxn] , dfn;
int ans[maxn] ;
void dfs(int u,int fa)
{
     L[u] = ++dfn;
     for (auto it: edge[u]) {
        if(it!=fa) dfs(it,u);
     }
     R[u] = dfn;
}
// ~segment tree
int col[maxn<<2];
int sum[maxn<<2];
void pushup(int rt, int l, int r) 
{
    if(col[rt] > 0) {
        sum[rt] = r - l + 1;
    } else if(l == r) {
        sum[rt] = 0;
    } else {
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
}
void update(int L,int R,int val,int l,int r,int rt)
{
    if(L <= l && r <= R) {
         col[rt] += val;
         pushup(rt,l,r);
         return;
    }
    int m = l + r >> 1;
    if( L <= m) update(L,R,val,lson);
    if( R > m)  update(L,R,val,rson);
    pushup(rt,l,r);
}
void solve(int u,int fa) 
{
    //枚举跟u 有关的 所有的操作
    for(auto it:adj[u]) {
        update(L[it],R[it],1,1,dfn,1);
    }
    ans[u] = sum[1];
    for(auto it: edge[u]) {
        if(it!=fa) solve(it,u);
    }
    //清空与u有关的所有操作
    for(auto it:adj[u]) {
        update(L[it],R[it],-1,1,dfn,1);
    }
}
int main()
{
    int n,m,u,v,a,b;
    scanf("%d%d",&n,&m);
    rep(i,n-1) scanf("%d%d",&u,&v),edge[u].push_back(v),edge[v].push_back(u);
    rep(i,m)  {
        scanf("%d%d",&a,&b);
        adj[a].push_back(a);
        adj[a].push_back(b);

        adj[b].push_back(a);
        adj[b].push_back(b);
    }
    dfs(1,-1);
    solve(1,-1);
    rep(i,n) printf("%d ",max(1,ans[i+1])-1);
    return 0;
}

求助

请问能否讲解一下这几个函数的作用，谢谢！

玄关！