Fork me on GitHub

「ZJOI2008」树的统计

发表于 | 分类于
字数统计: 912字 | 阅读时长 ≈ 5分钟

ZJOI-2008树的统计

Links there:ZJOI-2008树的统计

题意:要求实现这些操作

I. CHANGE u t : 把结点u的权值改为t

II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

注意：从点u到点v的路径上的节点包括u和v本身

其实是个树剖裸题啊.但是学了$LCT$这种更强大的东西么写起来岂不是更舒服.

其实和模板题差不多,注意pushup更新的时候维护信息时,每个节点的Mx和Sum先赋值为自己然后建立虚拟点Mx[0]=-INF.

傻逼的我还是调了好久才对,发现自己调$LCT$的题真心不熟.

P.S. LCT写起来比树剖优美多了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
using namespace std;
#define lc ch[u][0]
#define rc ch[u][1]

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}

///------------------head------------------
const int MAXN = 3e4+10;
int n,m,u[MAXN],v[MAXN];
inline char NextChar(void){
    char c=getchar();
    while(!isalpha(c)) c=getchar();
    return c;
}
struct LinkCutTree{
    int ch[MAXN][2],sum[MAXN],rev[MAXN],w[MAXN],fa[MAXN],Mx[MAXN];
    inline bool isRson(int u){return ch[fa[u]][1] == u;}
    inline bool isRoot(int u){return (ch[fa[u]][0] != u && ch[fa[u]][1] != u);}
    inline void Reverse(int u){rev[u] ^= 1;swap(lc,rc);}
    inline void pushdown(int u){if(rev[u]){if (lc) Reverse(lc); if(rc)Reverse(rc); rev[u]=0;}}
    inline void pushup(int u){sum[u]=sum[lc]+sum[rc]+w[u];Mx[u]=max(w[u],max(Mx[lc],Mx[rc]));}
    inline void Update(int u){if (!isRoot(u)) Update(fa[u]); pushdown(u);}
/* ----------- Splay part ------------*/
    inline void rotate(int u){
        int fau = fa[u],ffau = fa[fau],d = isRson(u);
        fa[u]=ffau; if (!isRoot(fau)) ch[ffau][isRson(fau)] = u;
        fa[ch[fau][d] = ch[u][d^1]] = fau;
        fa[ch[u][d^1] = fau] = u;
        pushup(fau); pushup(u);
    }
    inline void Splay(int u){
        Update(u);
        for (;(!isRoot(u));rotate(u)){
            if (!isRoot(fa[u]))
            rotate(isRson(fa[u])==isRson(u)?fa[u]:u);
        }
    }
/* ----------- LCT part ------------*/
    inline void access(int u){
        for(int f = 0; u; f = u,u = fa[u]){
            Splay(u);
            rc = f;
            pushup(u);
        }
    }
    inline void makeroot(int u){access(u);Splay(u);Reverse(u);}
    inline int find(int u){access(u);Splay(u);while(lc)pushdown(u),u=lc;return u;}
    inline void split(int x,int y){makeroot(x);access(y);Splay(y);}
    inline void link(int x,int y){makeroot(x);fa[x]=y;}
    inline void cut(int u,int v){split(u,v);if(fa[u]==v&&(!rc))fa[u]=ch[v][0]=0;pushup(v);}
}LCT;
signed main(signed argc, char *argv[]){
    //freopen("1.in","r",stdin);
    //freopen("my.out","w",stdout);
    n=read();rep(i,1,n-1){u[i]=read(),v[i]=read();}
    rep(i,1,n) LCT.w[i]=read(),LCT.sum[i]=LCT.Mx[i]=LCT.w[i];
    LCT.Mx[0]=-INT_MAX;
    rep(i,1,n-1) LCT.link(u[i],v[i]);
    m=read();
    rep(i,1,m)
    {
        char xx=NextChar();
        while(isalpha(xx)) {char t=xx;xx=getchar();if(!isalpha(xx)){xx=t;break;}}
        int x=read(),y=read();
        switch(xx){
            case 'X':{LCT.split(x,y);printf("%d\n",LCT.Mx[y]);break;}
            case 'M':{LCT.split(x,y);printf("%d\n",LCT.sum[y]);break;}
            case 'E':{LCT.Splay(x);LCT.w[x]=y;LCT.pushup(x);break;}
        }
    }
    return 0;
}