[BZOJ 3589] 动态树

Posted on | Edited on | In , | Views:

题目链接

BZOJ 3589

题目大意

给你一棵树，有两种操作，第一种是子树权值加，第二种是给你不超过五条链，让你求这些链的并集的权值和，这些链都是某个节点到根的一段，点数和询问数均$\le 200000$

做法

首先这种求链的权值和的题目肯定是要树链剖分的，子树加应该也是基础操作了。
那么怎么来求这5条链的交呢？去网上的题解看看大多都是LCA搞搞，细节可能会比较的多。
博主这里提供一个别样的思路。
我们树链剖分事实上就是把我们要求的那条链分解成不超过log段，dfn连续的区间，然后在线段树上查询对吧。
那么我们这里对这五条链也一样处理，在线段树上做区间置，表示这几段的值是我要的。由于是区间置，所以就自动去重了。
最后再查询一下就好了。
具体实现的话可以看代码。

代码

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (200005)
using namespace std;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false; 
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int n,tot,cnt,x,y,now,q,op,k; 
int head[N],nxt[N<<1],son[N<<1],size[N],ss[N],maxx[N],top[N],dfn[N],fa[N],dep[N];
inline void add(int x,int y){
    son[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void dfs1(int u){
    size[u]=1;
    int maxx=0;
    for (int p=head[u];p;p=nxt[p]){
        int v=son[p];
        if (v!=fa[u]){
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs1(v);
            size[u]+=size[v];
            if (size[v]>maxx){
                maxx=size[v];
                ss[u]=v;
            }
        } 
    }
}
void dfs2(int u,int f){
    dfn[u]=++cnt;
    top[u]=f;
    if (ss[u]){
        dfs2(ss[u],f);
    }
    for (int p=head[u];p;p=nxt[p]){
        int v=son[p];
        if (v!=ss[u]&&v!=fa[u]) dfs2(v,v);
    }
}
struct node{
    int l,r,lazy1,lazy2,sum,lazy;
}T[N<<2];
void build(int u,int L,int R){
    T[u].l=L,T[u].r=R;
    if (L==R) return;
    int mid=L+R>>1,v=u<<1;
    build(v,L,mid);
    build(v|1,mid+1,R); 
}
void pushdown(int u){
    if (T[u].lazy){
        int v=u<<1,x=T[u].lazy;
        T[u].lazy=0;
        T[v].lazy+=x,T[v|1].lazy+=x;
        T[v].sum+=(T[v].r-T[v].l+1)*x;
        T[v|1].sum+=(T[v|1].r-T[v|1].l+1)*x;
    }
}
void add(int u,int L,int R,int data){
    if (L<=T[u].l&&T[u].r<=R){
        T[u].sum+=(T[u].r-T[u].l+1)*data;
        T[u].lazy+=data;
        return;
    }
    pushdown(u);
    int mid=T[u].l+T[u].r>>1,v=u<<1;
    if (L<=mid) add(v,L,R,data);
    if (R>mid) add(v|1,L,R,data);
    T[u].sum=T[v].sum+T[v|1].sum;
}
void change(int u,int L,int R){
    if (L<=T[u].l&&T[u].r<=R){
        T[u].lazy2=now;
        T[u].lazy1=now;
        return;
    }
    T[u].lazy2=now;
    int mid=T[u].l+T[u].r>>1,v=u<<1;
    if (L<=mid) change(v,L,R);
    if (R>mid) change(v|1,L,R); 
}
int query(int u){
    //printf("%d %d %d\n",T[u].l,T[u].r,T[u].sum);
    if (T[u].lazy1==now){
        //printf("query %d %d %d\n",T[u].l,T[u].r,T[u].sum);
        return T[u].sum;
    }
    pushdown(u);
    int v=u<<1,ret=0;
    if (T[v].lazy2==now) ret+=query(v);
    if (T[v|1].lazy2==now) ret+=query(v|1);
    return ret;
}
void jump(int x,int y){
    while (top[x]!=top[y]){
        change(1,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    change(1,dfn[y],dfn[x]);
} 
int main(){
    read(n);
    for (int i=1;i<n;i++){
        read(x),read(y);
        add(x,y),add(y,x);
    }
    build(1,1,n);
    dfs1(1);
    dfs2(1,1);
    //for (int i=1;i<=n;i++) printf("%d ",dfn[i]);
    //puts("");
    read(q);
    while (q--){
        read(op);
        if (op==0){
            read(x),read(y);
            add(1,dfn[x],dfn[x]+size[x]-1,y);
        }
        if (op==1){
            read(k);
            now++;
            for (int i=1;i<=k;i++){
                read(x),read(y);
                if (dep[x]<dep[y]) jump(y,x);
                else jump(x,y);
            }
            int tt=query(1);
            if (tt<0) tt+=(1<<31);
            printf("%d\n",tt);
        } 
    }
    return 0;
}