树链剖分 模板题

#include 
     
      using namespace std;const int N = 5e4 + 10;#define gc getchar()#define lson jd << 1#define rson jd << 1 | 1#define important T[jd].w = T[lson].w + T[rson].wstruct Node_1{    int siz, son, fa, deep, tree, toop;}P[N];struct Node_2{    int v, nxt;}G[N << 1];struct Node_3{    int l, r, f, w;}T[N << 2];int n, Ti, now = 1, head[N], tim, bef[N];int answer;inline int read(){    int x = 0; char c = gc;    while(c < '0' || c > '9') c = gc;    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;    return x;}inline void add(int u, int v){     G[now].v = v;     G[now].nxt = head[u];     head[u] = now ++;}void dfs_find_son(int u, int fa, int dep){    P[u].fa = fa;    P[u].deep = dep;    P[u].siz = 1;    for(int i = head[u]; ~ i; i = G[i].nxt){        int v = G[i].v;        if(v != fa) {            dfs_find_son(v, u, dep + 1);            P[u].siz += P[v].siz;            if(P[v].siz > P[P[u].son].siz) P[u].son = v;        }    }}void dfs_to_un(int u, int tp){    P[u].toop = tp;    P[u].tree = ++ tim;    bef[tim] = u;    if(!P[u].son) return ;    dfs_to_un(P[u].son, tp);    for(int i = head[u]; ~ i; i = G[i].nxt){        int v = G[i].v;        if(v != P[u].son && v != P[u].fa) dfs_to_un(v, v);    }}void down(int jd){    int F = T[jd].f;    T[lson].w += (T[lson].r - T[lson].l + 1) * F;    T[rson].w += (T[rson].r - T[rson].l + 1) * F;    T[lson].f += F;    T[rson].f += F;    T[jd].f = 0;}void Sec_G(int l, int r, int jd, int x, int y){    if(x <= l && r <= y){        int yj = (r - l) + 1;        T[jd].w += yj;        T[jd].f ++;        return ;    }    if(T[jd].f) down(jd);    int mid = (l + r) >> 1;    if(x <= mid) Sec_G(l, mid, lson, x, y);    if(y > mid) Sec_G(mid + 1, r, rson, x, y);    important;}inline void Sec_G_imp(int x, int y){    int tp1 = P[x].toop, tp2 = P[y].toop;    while(tp1 != tp2){        if(P[tp1].deep < P[tp2].deep) swap(x, y), swap(tp1, tp2);        Sec_G(1, n, 1, P[tp1].tree, P[x].tree);        x = P[tp1].fa;        tp1 = P[x].toop;    }    if(P[x].deep < P[y].deep) Sec_G(1, n, 1, P[x].tree, P[y].tree);    else Sec_G(1, n, 1, P[y].tree, P[x].tree);    return ;}void Ask_ans(int l, int r, int jd){    if(l == r) {        answer = max(answer, T[jd].w);        return ;        }    if(T[jd].f) down(jd);    int mid = (l + r) >> 1;    Ask_ans(l, mid, lson);    Ask_ans(mid + 1, r, rson);}int main(){    n = read(); Ti = read();    for(int i = 1; i <= n; i ++) head[i] = -1;    for(int i = 1; i < n; i ++){        int u = read(), v = read();        add(u, v); add(v, u);    }    dfs_find_son(1, 0, 1);    dfs_to_un(1, 1);    while(Ti --){        int x = read(), y = read();        Sec_G_imp(x, y);    }    Ask_ans(1, n, 1);    printf("%d", answer);    return 0;}