树上问题

发表于 更新于 阅读次数：

树上问题是一类重要的问题，大体上可分为：

1.用数据结构，如树剖、LCT、树上倍增来维护路径/子树信息。

2.用长链剖分/启发式合并/dsuontree/点分治/边分治等方法快速合并各子树信息。

3.与其他算法结合，如树上高斯消元/树上莫队/树上斜率优化等。

口胡完毕。

然而树上问题往往千变万化，虽然方法就是这些，但是维护的东西不一样可能做法就千差万别，而且对于码力也有一定的要求。

这里是一个杂题集，慢慢的更题。

比如定个小目标，先把蒋队的题写完。

树上问题选讲 by JXL

幻想乡战略游戏

题目链接

solution:很容易可以相到点分树，因为点分树上一对父子所管理的区域是可以快速合并的，大概就是所有点到父亲的距离容斥掉自己这个区域点到父亲的距离和这样子，需要维护:

1.该区域的点到重心距离*权值和。

2.该区域点到重心父亲距离*权值和。

3.该区域点权值和。

code:

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
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=1e6+10;
struct edge{
    int next,to,w,rt;
}e[N];
int head[N],tot=1;
void add(int x,int y,int z){
    e[++tot].next=head[x];e[tot].to=y;head[x]=tot;e[tot].w=z;
}
int ST[N][21],lg[N],id[N][21],oula[N],cnt,deep[N];
void pre(int u,int fa){
    oula[u]=++cnt;
    ST[cnt][0]=deep[u];id[cnt][0]=u;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa){
            deep[e[i].to]=deep[u]+e[i].w;
            pre(e[i].to,u);
            ST[++cnt][0]=deep[u];id[cnt][0]=u;
        }
}
void build(){
    register int i,j;
    for(i=2;i<=cnt;i++)lg[i]=lg[i>>1]+1;
    for(j=1;j<=lg[cnt];j++)
        for(i=1;i+(1<<j)-1<=cnt;i++){
            if(ST[i][j-1]<ST[i+(1<<(j-1))][j-1])ST[i][j]=ST[i][j-1],id[i][j]=id[i][j-1];
            else ST[i][j]=ST[i+(1<<(j-1))][j-1],id[i][j]=id[i+(1<<(j-1))][j-1];
        }
}
int lca(int x,int y){
    x=oula[x];y=oula[y];
    if(x>y)swap(x,y);
    int len=lg[y-x+1];
    return ST[x][len]<ST[y-(1<<len)+1][len]?id[x][len]:id[y-(1<<len)+1][len];
}
ll dis(int x,int y){
    int Lca=lca(x,y);
    return 1ll*deep[x]+deep[y]-2*deep[Lca];
}
int vis[N],root,siz[N],Sum;
void getsum(int u,int fa){
    Sum++;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa&&!vis[e[i].to])
            getsum(e[i].to,u);
}
int maxson[N],Fa[N];
void getroot(int u,int fa){
    siz[u]=1;maxson[u]=0;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa&&!vis[e[i].to]){
            getroot(e[i].to,u);
            maxson[u]=max(maxson[u],siz[e[i].to]);
            siz[u]+=siz[e[i].to];
        }
    maxson[u]=max(maxson[u],Sum-siz[u]);
    if(maxson[u]<maxson[root])root=u;
}
void solve(int u){
    vis[u]=1;
    for(int i=head[u];i;i=e[i].next)
        if(!vis[e[i].to]){
            root=Sum=0;
            getsum(e[i].to,0);
            getroot(e[i].to,0);
            Fa[root]=u;
            e[i].rt=root;
            solve(root);
        }
}
ll sum[N],f[N],g[N];
void addup(int u,int val){
    int x=u;
    sum[u]+=val;
    while(Fa[x]){
        sum[Fa[x]]+=val;
        f[Fa[x]]+=val*dis(Fa[x],u);
        g[x]+=val*dis(Fa[x],u);
        x=Fa[x];
    }
}

ll count(int u){
    int x=u;
    ll ans=f[u];
    while(Fa[x]){
        ans+=f[Fa[x]]-g[x];
        ans+=(sum[Fa[x]]-sum[x])*dis(u,Fa[x]);
        x=Fa[x];
    }
    return ans;
}

ll query(int u){
    ll now=count(u);
    for(int i=head[u];i;i=e[i].next){
        if(!e[i].rt)continue;
        if(count(e[i].to)<now)
        return query(e[i].rt);
    }
    
    return now;
}
int n,m;
signed main(){
    register int i;
    n=read();m=read();
    for(i=1;i<n;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z);add(y,x,z);
    }
    pre(1,0);
    build();
    maxson[0]=2147483647;
    getsum(1,0);
    getroot(1,0); 
    int Root=root;
    solve(root);
    for(i=1;i<=m;i++){
        int x=read(),y=read();
        addup(x,y);
        cout<<query(Root)<<'\n';	
    }
    return 0;
}

考试T2

题意：给定两颗树，询问\sum_{i=1}^{n}\sum_{j=1}^{n}dis1(i,j)*dis2(i,j)。

solution:边分治第一颗树，两边黑白染色，在另一颗树上加上权之后便变成询问第二颗树上异色点对的带权距离和。

于是每次在第二颗树上建虚树后树上dp即可。

切记：多叉转二叉。

code:

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include<cstdio>
#include<iostream>
#include<cstring
#include<algorithm>
using namespace std;
static char buf[100000],*pa,*pd;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
#define ll long long
const int N=410000,P=1e9+7;
struct edge{
    int from,next,to;
    ll w;
}e[N*10],E[N<<2];
int head[N],Head[N],HEAD[N],tot=1,vis[N];
void add1(int x,int y,int z){/*cerr<<x<<' '<<y<<' '<<z<<'\n'*/;e[++tot].next=head[x];e[tot].to=y;head[x]=tot;e[tot].w=z;e[tot].from=x;}//Tree1
void add2(int x,int y,int z){e[++tot].next=Head[x];e[tot].to=y;Head[x]=tot;e[tot].w=z;e[tot].from=x;}//Tree2
int TOT;
void add3(int x,int y,int z){/*cerr<<x<<' '<<y<<'\n';*/E[++TOT].next=HEAD[x];E[TOT].to=y;HEAD[x]=TOT;E[TOT].w=z;}//xu Tree
int Sum,root,n,siz[N],mxsiz[N];
ll ans;
struct OU{
    int deep[N],deep2[N],ST[N][21],lg[N],id[N][21],oula[N],cnt,ID;
    void pre(int u,int fa){
        oula[u]=++cnt;
        ST[cnt][0]=deep2[u];id[cnt][0]=u;
        int bg=ID?Head[u]:head[u];
        for(int i=bg;i;i=e[i].next)
            if(e[i].to!=fa){
                deep2[e[i].to]=deep2[u]+1;
                deep[e[i].to]=deep[u]+e[i].w;
                pre(e[i].to,u);
                ST[++cnt][0]=deep2[u];id[cnt][0]=u;
            }
    }
    void build(){
        register int i,j;
        for(i=2;i<=cnt;i++)lg[i]=lg[i>>1]+1;
        for(j=1;j<=lg[cnt];j++)
            for(i=1;i+(1<<j)-1<=cnt;i++){
                if(ST[i][j-1]<ST[i+(1<<(j-1))][j-1])ST[i][j]=ST[i][j-1],id[i][j]=id[i][j-1];
                else ST[i][j]=ST[i+(1<<(j-1))][j-1],id[i][j]=id[i+(1<<(j-1))][j-1];
            }
    }
    int lca(int x,int y){
        x=oula[x];y=oula[y];
        if(x>y)swap(x,y);
        int len=lg[y-x+1];
        if(ST[x][len]<ST[y-(1<<len)+1][len])return id[x][len];
        return id[y-(1<<len)+1][len];
    }
    ll dis(int x,int y){
        int Lca=lca(x,y);
        return deep[x]+deep[y]-2*deep[Lca];
    }
}Tree[2];
void getsum(int u,int fa){
    Sum++;
    for(int i=head[u];i;i=e[i].next)
        if(!vis[i]&&e[i].to!=fa){
            getsum(e[i].to,u);
        }
}

int MX,B;
void getroot(int u,int fa){
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
        if(!vis[i]&&e[i].to!=fa){
            getroot(e[i].to,u);
            siz[u]+=siz[e[i].to];
            if(siz[e[i].to]>MX&&siz[e[i].to]<=(Sum+1)/2)MX=siz[e[i].to],B=i;
        }
//	cerr<<MX<<'\n';
    
}
void Getroot(int u){
    MX=B=Sum=0;
    getsum(u,0);
    getroot(u,0);
    vis[B]=vis[B^1]=1;
}

int a[N],val[N],c[N],sta[N],top;
bool cmp(const int &x,const int &y){
    return Tree[1].oula[x]<Tree[1].oula[y];
}

ll f[N][2];//当前点黑/白的 权值 和 
ll cot[N][2];//数量 
ll g[N][2];//深度 和
ll h[N][2];//权值*深度 和。
void ins(int id){
    if(top<=1){sta[++top]=id;return;}
    while(top>1&&Tree[1].deep2[Tree[1].lca(sta[top],id)]<Tree[1].deep2[sta[top-1]])add3(sta[top-1],sta[top],Tree[1].dis(sta[top],sta[top-1])),top--;
    int Lca=Tree[1].lca(sta[top],id);
    if(top>1&&Tree[1].deep2[Lca]<Tree[1].deep2[sta[top]])add3(Lca,sta[top],Tree[1].dis(Lca,sta[top])),top--;
    if(sta[top]!=Lca)sta[++top]=Lca;
    sta[++top]=id;
} 
void dfs(int u){
    //cerr<<u<<'\n';
    cot[u][0]=f[u][0]=g[u][0]=h[u][0]=0;
    cot[u][1]=f[u][1]=g[u][1]=h[u][1]=0;
    if(c[u]!=-1){
        cot[u][c[u]]++;
        f[u][c[u]]+=val[u];	
    }
    for(int i=HEAD[u];i;i=E[i].next){
        int v=E[i].to;
        dfs(v);
        
        (g[v][1]+=cot[v][1]*E[i].w%P)%=P;
        (g[v][0]+=cot[v][0]*E[i].w%P)%=P;
        (h[v][0]+=f[v][0]*E[i].w%P)%=P;
        (h[v][1]+=f[v][1]*E[i].w%P)%=P;
        
        (ans+=f[u][0]*g[v][1]%P+f[u][1]*g[v][0]%P+f[v][0]*g[u][1]%P+f[v][1]*g[u][0]%P)%=P;
        (ans+=h[u][0]*cot[v][1]+h[u][1]*cot[v][0]+h[v][0]*cot[u][1]+h[v][1]*cot[u][0])%=P;

        for(int k=0;k<=1;k++){
            (f[u][k]+=f[v][k])%=P;
            (cot[u][k]+=cot[v][k])%=P;
            (g[u][k]+=g[v][k])%=P;
            (h[u][k]+=h[v][k])%=P;
        }
    }
    HEAD[u]=0;
}
int cnt;
void color(int u,int fa,int kind,int rt){
    if(u<=n){
        a[++cnt]=u;
        val[u]=Tree[0].dis(u,rt);c[u]=kind;
    }
    for(int i=head[u];i;i=e[i].next)
        if(!vis[i]&&e[i].to!=fa){
            color(e[i].to,u,kind,rt);
        }
}

void cal(){
    register int i;TOT=0;
    sort(a+1,a+1+cnt,cmp);
    if(a[1]!=1)ins(1);
 	for(i=1;i<=cnt;i++)ins(a[i]);
 	while(--top){
 		add3(sta[top],sta[top+1],Tree[1].dis(sta[top],sta[top+1]));
    }
 	dfs(1);
 	for(i=1;i<=cnt;i++)HEAD[a[i]]=0,c[a[i]]=-1;
}
int ans2=0;
void solve(int Id){
    cnt=0;
    int u=e[Id].from,v=e[Id].to;
    //cerr<<u<<' '<<v<<'\n';
    color(u,0,0,u);
    color(v,0,1,u);
    /*for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
			if(c[i]!=c[j]&&c[i]!=-1&&c[j]!=-1)ans2+=Tree[1].dis(i,j)*Tree[0].dis(i,j);
		}*/
    
    cal();
    Getroot(u);if(B)solve(B);
    Getroot(v);if(B)solve(B);
}
int nodecnt,t,x[N],y[N],z[N];
void prepare(int u,int fa){
    int now=0;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa){
            if(!now){
                t++;
                x[t]=u;y[t]=++nodecnt;
                t++;
                x[t]=nodecnt;y[t]=e[i].to;z[t]=e[i].w;
                now=1;
            }
            else{
                t++;
                x[t]=nodecnt;y[t]=++nodecnt;
                t++;
                x[t]=nodecnt;y[t]=e[i].to;z[t]=e[i].w;
            }
        }
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa)
            prepare(e[i].to,u);
}
signed main(){
    memset(c,-1,sizeof(c));
    freopen("transport.in","r",stdin);
    freopen("transport.out","w",stdout);
    n=read();
    register int i;nodecnt=n;
    for(i=1;i<n;i++){
        int x=read(),y=read(),z=read();
        add1(x,y,z);add1(y,x,z);
    }
    prepare(1,0);tot=1;memset(head,0,sizeof(head));
    for(i=1;i<=t;i++)add1(x[i],y[i],z[i]),add1(y[i],x[i],z[i]);
    
    for(i=1;i<n;i++){
        int x=read(),y=read(),z=read();
        add2(x,y,z);add2(y,x,z);
    }
    Tree[1].ID=1;
    Tree[0].pre(1,0);Tree[0].build();
    Tree[1].pre(1,0);Tree[1].build();
    Getroot(1);
    solve(B);
    cout<<ans*2%P;
    return 0;
}
/*
7
1 2 1
2 3 2
1 4 4
3 5 4
4 6 5
6 7 2
1 2 5
1 3 3
2 4 1
4 5 1
4 6 1
2 7 1
*/

小清新数据结构题

题目链接

solution:记录一种蛮巧妙的解法，考虑根恒为1的做法，设根到点路径上点依次编号1,2,3,4..k，a[u][i]表示以i为根时u的子树大小。那么改变量就是\sum_{i=1}^{k}(a[i][1]+delta)^2-a[i][1]^2=\sum_{i=1}^{k}delta^2+2*delta*a[i][1]，把a当做权值，维护点到根的链上权值和即可。

然后考虑换根为u，发现1->u路径上的点子树大小才发生改变，并且：

1.a[u][u]=a[1][1]=sum

2.a[1][1]-a[i+1][1]=a[i][u]

现在答案ans_u=ans1+\sum_{i=1}^{k}a[i][u]^2-\sum_{i=1}^{k}a[i][1]^2

消去a[1][1]^2和a[u][u]^2：

=ans1-\sum_{i=2}^{k}a[i][1]^2+\sum_{i=1}^{k-1}(a[1]-a[i+1][1])^2

=ans1-\sum_{i=2}^{k}a[i][1]^2+\sum_{i=2}^{k}(a[1][1]-a[i][1])^2

=ans1+\sum_{i=2}^{k}(a[1][1]^2-2*a[1][1]*a[i][1])

可以形如前面树剖维护即可。

code:

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
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=410000;
#define int long long
struct edge{
    int to,next;
}e[N];
int head[N],tot;
void add(int x,int y){
    e[++tot].to=y;e[tot].next=head[x];head[x]=tot;
}
int val[N];
int nowans,sum[N];
void dfs(int u,int fa){
    sum[u]=val[u];
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa){
            dfs(e[i].to,u);
            sum[u]+=sum[e[i].to];
        }
    nowans+=sum[u]*sum[u];
}
int deep[N],cnt,son[N],top[N],seg[N],fa[N],siz[N],n,m;
void dfs1(int u,int fath){
    fa[u]=fath;
    siz[u]=1;
    deep[u]=deep[fath]+1;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fath){
            dfs1(e[i].to,u);
            siz[u]+=siz[e[i].to];
            if(siz[e[i].to]>siz[son[u]])son[u]=e[i].to;
        }
}
int a[N];
void dfs2(int u,int topnow){
    top[u]=topnow;
    seg[u]=++cnt;
    a[cnt]=sum[u];
    if(son[u])dfs2(son[u],topnow);
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa[u]&&e[i].to!=son[u])
            dfs2(e[i].to,e[i].to);
}
#define ls id<<1
#define rs id<<1|1
#define mid ((l+r)>>1)
int sumval[N<<2],tag[N<<2];
void up(int id){
    sumval[id]=sumval[ls]+sumval[rs];
}
void down(int l,int r,int id){
    tag[ls]+=tag[id];tag[rs]+=tag[id];
    sumval[ls]+=tag[id]*(mid-l+1);
    sumval[rs]+=tag[id]*(r-mid);
    tag[id]=0;
}
void build(int l,int r,int id){
    if(l==r){
        sumval[id]=a[l];
        return;
    }
    build(l,mid,ls);
    build(mid+1,r,rs);
    up(id);
}
void addup(int l,int r,int x,int y,int z,int id){
    if(l>=x&&r<=y){
        tag[id]+=z;
        sumval[id]+=(r-l+1)*z;
        return;
    }
    down(l,r,id);
    if(x<=mid)addup(l,mid,x,y,z,ls);
    if(y>mid)addup(mid+1,r,x,y,z,rs);
    up(id);
}
int query(int l,int r,int x,int y,int id){
    if(l>=x&&r<=y){
        return sumval[id];
    }
    down(l,r,id);
    int ans=0;
    if(x<=mid)ans+=query(l,mid,x,y,ls);
    if(y>mid)ans+=query(mid+1,r,x,y,rs);
    return ans;
}
int Query(int x,int y){
    int ans=0;
    while(deep[top[x]]>deep[y]){
        ans+=query(1,n,seg[top[x]],seg[x],1);
        x=fa[top[x]];
    }
    ans+=query(1,n,seg[y],seg[x],1);
    return ans;
}
void Addup(int x,int y,int z){
    while(deep[top[x]]>deep[y]){
        addup(1,n,seg[top[x]],seg[x],z,1);
        x=fa[top[x]];
    }
    addup(1,n,seg[y],seg[x],z,1);
}
void change(int x,int y){
    int del=y-val[x];val[x]=y;
    nowans+=deep[x]*del*del+Query(x,1)*2*del;
    Addup(x,1,del);
}
void ques(int u){
    int a1=query(1,n,seg[1],seg[1],1);
    cout<<nowans+(deep[u]-1)*a1*a1-a1*2*(Query(u,1)-a1)<<'\n';
}
signed main(){
    register int i;
    n=read();m=read();
    for(i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    for(i=1;i<=n;i++)val[i]=read();
    dfs(1,0);	
    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);
    for(i=1;i<=m;i++){
        int opt=read();
        if(opt==1){
            int x=read(),y=read();
            change(x,y);
        }
        else{
            int x=read();
            ques(x);
        }
    }
    return 0;
}

天天爱跑步

题目链接

solution:首先链上加肯定树上查分，化出式子后发现每次要就是合并两个桶，答案就是当前桶某个位置的值。直接线段树合并即可。

code:

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=810000,limit=1e9;
struct edge{
    int to,next;
}e[N];
int head[N],tot;
void add(int x,int y){
    e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
} 
int n,m,T[N],fa[N],ST[N][21],deep[N],id[N][21],dfn[N],cnt,lg[N];
void dfs(int u,int fath){
    fa[u]=fath;
    deep[u]=deep[fath]+1;
    dfn[u]=++cnt;
    ST[cnt][0]=deep[u];
    id[cnt][0]=u;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fath){
            dfs(e[i].to,u);
            ST[++cnt][0]=deep[u];
            id[cnt][0]=u;
        }
}
void build(){
    register int i,j;
    for(i=2;i<=cnt;i++)lg[i]=lg[i>>1]+1;
    for(j=1;j<=lg[cnt];j++)
        for(i=1;i+(1<<j)-1<=cnt;i++)
            if(ST[i][j-1]<ST[i+(1<<(j-1))][j-1])ST[i][j]=ST[i][j-1],id[i][j]=id[i][j-1];
            else ST[i][j]=ST[i+(1<<(j-1))][j-1],id[i][j]=id[i+(1<<j-1)][j-1];
}
int lca(int x,int y){
    x=dfn[x],y=dfn[y];
    if(x>y)swap(x,y);
    int len=lg[y-x+1];
    if(ST[x][len]<ST[y-(1<<len)+1][len])return id[x][len];
    return id[y-(1<<len)+1][len];
}
vector<int> v1[N],v2[N],d1[N],d2[N];
int segcnt,Rs[N*20],Ls[N*20],sum[N*20];
struct SegmentTree{
    int root;	
    #define ls Ls[id]
    #define rs Rs[id]
    #define mid ((l+r)>>1)
    const int limit=1e9;
    int ins(int l,int r,int x,int z,int id){
        if(!id)id=++segcnt;
        if(l==r){
            sum[id]+=z;
            return id;
        }
        if(x<=mid)ls=ins(l,mid,x,z,ls);
        else rs=ins(mid+1,r,x,z,rs);
        return id;
    }
    int query(int l,int r,int x,int id){
        if(!id)return 0;
        if(l==r){
            return sum[id];
        }
        if(x<=mid)return query(l,mid,x,ls);
        return query(mid+1,r,x,rs);
    }
}seg1[310000],seg2[310000];
int merge(int x,int y,int l,int r){
    if(!x||!y)return x+y;
    if(l==r){
        sum[x]+=sum[y];
        return x;
    }
    Ls[x]=merge(Ls[x],Ls[y],l,mid);
    Rs[x]=merge(Rs[x],Rs[y],mid+1,r);
    return x;
}
int ans[N];
void Dfs(int u){
    for(int i=0;i<d1[u].size();i++)seg1[u].root=seg1[u].ins(-limit,limit,d1[u][i],-1,seg1[u].root);
    for(int i=0;i<d2[u].size();i++)seg2[u].root=seg2[u].ins(-limit,limit,d2[u][i],-1,seg2[u].root);
        
    for(int i=0;i<v1[u].size();i++)seg1[u].root=seg1[u].ins(-limit,limit,v1[u][i],1,seg1[u].root);
    for(int i=0;i<v2[u].size();i++)seg2[u].root=seg2[u].ins(-limit,limit,v2[u][i],1,seg2[u].root);
        
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa[u]){
            int v=e[i].to;
            Dfs(v);
            seg1[u].root=merge(seg1[u].root,seg1[v].root,-limit,limit);
            seg2[u].root=merge(seg2[u].root,seg2[v].root,-limit,limit);		
        }
        
    ans[u]=seg1[u].query(-limit,limit,deep[u]+T[u],seg1[u].root)+seg2[u].query(-limit,limit,deep[u]-T[u],seg2[u].root);
    
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
    n=read();m=read();
    register int i;
    for(i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    dfs(1,0);
    build();
    for(i=1;i<=n;i++)T[i]=read();
    for(i=1;i<=m;i++){
        int x=read(),y=read();
        int Lca=lca(x,y);
        v1[x].push_back(deep[x]);
        v2[y].push_back(2*deep[Lca]-deep[x]);
        d1[Lca].push_back(deep[x]);
        d2[fa[Lca]].push_back(2*deep[Lca]-deep[x]);
    }
    Dfs(1);
    for(i=1;i<=n;i++)cout<<ans[i]<<' ';
    return 0;
}

树上游戏

题目链接

solution:首先很容易想到一个点分治/边分治的O(nlogn)做法，这里只记载一下O(n)的树上差分做法。考虑每个颜色的贡献，设删去所有该颜色后i点的连通块大小为z，因为只有跨连通块的会产生贡献，那么贡献就是n-block。然后可以看出i点与fa(i)所处联通块基本相同，除了颜色为color(fa)的联通块以外。所以我们可以维护每个点在切掉color(fa)后的连通块大小(相当于u是这个连通块的根)，最后先处理出根的答案，每次O(1)换根修改即可。

暂时LuoguRank1

code:

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
static char buf[100000],*pa,*pd;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
    register int x(0);register char c(gc);
    while(c>'9'||c<'0')c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return x;
}
const int N=210000,limit=100000;
struct edge{
    int to,next;
}e[N];
int head[N],tot;
void add(int x,int y){
    e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
}
int n,c[N],siz[N],cut[N],blocksiz[N],b[N];
long long ans[N],all;
void dfs(int u,int fa){
    siz[u]=1;
    int tmp=cut[c[fa]];
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa){
            dfs(e[i].to,u);
            siz[u]+=siz[e[i].to];
        }
    cut[c[u]]++;
    if(fa){
        blocksiz[u]=siz[u]-(cut[c[fa]]-tmp);
        cut[c[fa]]+=blocksiz[u];
    }
    //如果32行的句子扔在这里，那么当c[u]==c[fa[u]]时u就会被删两遍。一次作为“被c[fa]隔开的连通块”，一次作为“c[u]连通块的根”。
}
void getans(int u,int fa){
    all+=blocksiz[u]-b[c[fa]];
    int tmp=b[c[fa]];
    b[c[fa]]=blocksiz[u];
    ans[u]=1ll*n*limit-all+b[c[u]];
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa)
            getans(e[i].to,u);
    b[c[fa]]=tmp;
    all-=blocksiz[u]-b[c[fa]];
} 
signed main(){
    register int i;
    n=read();
    for(i=1;i<=n;i++)c[i]=read();
    for(i=1;i<n;i++){
        int x=read(),y=read();add(x,y);add(y,x);
    }
    dfs(1,0);
    for(i=1;i<=limit;i++)all+=n-cut[i],b[i]=n-cut[i]; 
    getans(1,0);
    for(i=1;i<=n;i++)cout<<ans[i]<<'\n'; 
    return 0;
}

NOI2014购票

题目链接

solution:首先如果没有L的限制，那么就是个树上斜率优化的板子了，具体操作就是从上往下转移，每次维护到根的那条链的凸包，用二分插入来支持O(1)回溯，至于斜率不单调只要凸包上二分即可。但是这个L的限制很恶心，有一种思路很简单的做法，就是维护一棵以深度为下标的线段树，线段树上每个节点是一段链组成的凸包，然后找到当前点L对应的区间，拎出来logn个凸包后分别在上面二分即可，复杂度是O(nlog^2n)。

这里有两个坑爹的细节，第一就是Windows和Linux在不给longlong变量赋值的情况下，他们的初值是不一样的，windows差不多是个3e6级别，而Linux是1.5e14级别，自闭到怀疑luogu评测机抽风了；第二就是因为每次要回溯线段树上logn个节点，所以回溯用的栈要开nlogn。

少有的写了一次指针开不等长数组(vector左闭右开不符合我的习惯)

code:

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
#define ll long long
const int N=410000;
struct edge{
    int to,next,w;
}e[N];
int head[N],tot;
void add(int x,int y,int z){
    e[++tot].to=y;e[tot].next=head[x];head[x]=tot;e[tot].w=z;
}
int n,tp,l[N],p[N],Q[N];
ll f[N],deep[N];
void pre(int u){
    for(int i=head[u];i;i=e[i].next){
        deep[e[i].to]=deep[u]+e[i].w;
        pre(e[i].to);
    }
}
#define ls id<<1
#define rs id<<1|1
#define mid ((l+r)>>1)
int fa[N<<2],seg[N<<2];
struct node{int i,j,x,y,siz;};
node sta[N<<5],*q[N<<2],tmp[N<<5],*t=tmp;
void build(int l,int r,int id){
    q[id]=t;
    t+=r-l+2;
    if(l==r){
        seg[l]=id;
        return;
    }
    fa[ls]=fa[rs]=id;
    build(l,mid,ls);
    build(mid+1,r,rs);
}

int top,siz[N<<2],qdeep[N],len;
const double eps=1e-8;
double slope(node a,node b){
    return (double)(a.y-b.y)/(double)(eps+a.x-b.x); 
}
void ins(int u,int x,int y){
    int c=u;
    while(u){
        int pre=1;
        if(siz[u]<2)pre=siz[u];		
        else{	
            int l=2,r=siz[u];
            node now;now.x=x,now.y=y; 
            while(l<=r){
                if(slope(now,q[u][mid])>slope(q[u][mid],q[u][mid-1]))pre=mid,l=mid+1;
                else r=mid-1;
            }
        } 
        sta[++top]=(node){u,pre+1,q[u][pre+1].x,q[u][pre+1].y,siz[u]};
        siz[u]=pre+1;
        q[u][pre+1].x=x,q[u][pre+1].y=y;
        u=fa[u];
    }	
}
node Min(node a,node b,int k){
    if(a.y-a.x*k<b.y-b.x*k)return a;
    return b;
}
const ll INF=1e18;
node query(int l,int r,int x,int y,int k,int id){
    node ans;
    ans.y=INF;
    ans.x=0;//注意这里。。。
    if(l>=x&&r<=y){
        ans=q[id][1];
        int L=2,R=siz[id];
        while(L<=R){
            int Mid=(L+R)>>1;
            if(slope(q[id][Mid],q[id][Mid-1])<=k)ans=q[id][Mid],L=Mid+1;
            else R=Mid-1; 
        }
        return ans;
    } 
    if(x<=mid)ans=Min(ans,query(l,mid,x,y,k,ls),k);
    if(y>mid)ans=Min(ans,query(mid+1,r,x,y,k,rs),k);
    return ans;
}
void re(node u){
    siz[u.i]=u.siz;
    q[u.i][u.j].x=u.x,q[u.i][u.j].y=u.y;
} 
void dfs(int u){
    int tmp=top;
    if(u!=1){
        int s=lower_bound(qdeep+1,qdeep+len,deep[u]-l[u])-qdeep; 
        node from=query(1,n,s,len,p[u],1);
        f[u]=1ll*from.y+p[u]*(deep[u]-from.x)+Q[u];
    }
    ins(seg[++len],deep[u],f[u]);
    qdeep[len]=deep[u];
    //更新+插入 
    for(int i=head[u];i;i=e[i].next)
        dfs(e[i].to);
    //删除 
    while(top>tmp)re(sta[top]),top--;	
    qdeep[len--]=0;
}
signed main(){
    register int i;
    n=read();tp=read();
    build(1,n,1);
    for(i=2;i<=n;i++){
        int x=read(),z=read();add(x,i,z);
        p[i]=read();Q[i]=read();l[i]=read();
    }
    pre(1);
    dfs(1);
    for(i=2;i<=n;i++)cout<<f[i]<<'\n';
    return 0;
}

APIO2018铁人两项

题目链接

solution:圆方树裸题，对于这种"两点之间简单路径"的统计大多是圆方树，因为一个两个点之间的简单路径能包含的元素就是这两点间所有点双内的点。然后看此题(a,c)的贡献就是这些点双的siz和，即方点权值和，不过要减去割点(因为作为圆点被两个方点连了)，还要减去起始点和终止点。

这里一个巧妙的方法就是直接把圆点权值设成-1，然后直接求所有"起终点都为圆点"的路径权值和即可。

code:

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=810000;
struct Edge{
    struct edge{
        int to,next,w;
    }e[N];
    int head[N],tot;
    void add(int x,int y){
        e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
    }
}E[2];
int dfn[N],low[N],t,BCC,sta[N],top,n,m;
long long val[N],sumval[N];
void ADD(int u){
    val[BCC]++;
    E[1].add(u,BCC);E[1].add(BCC,u);
}
void pre(int u,int fa){
    low[u]=dfn[u]=++t;sta[++top]=u;
    for(int i=E[0].head[u];i;i=E[0].e[i].next){
        int v=E[0].e[i].to;
        if(!dfn[v]){
            pre(v,u);low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                BCC++;
                ADD(u);
                while(sta[top]!=v)
                    ADD(sta[top--]);
                ADD(sta[top--]);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
long long sumsiz[N],ans;
int vis[N];
void dfs(int u,int fa){
    vis[u]=1;
    if(u<=n)sumsiz[u]=1,val[u]=-1,sumval[u]=-1;
    for(int i=E[1].head[u];i;i=E[1].e[i].next){
        int v=E[1].e[i].to;
        if(v!=fa){
            dfs(v,u);
            ans+=sumval[u]*sumsiz[v]+sumval[v]*sumsiz[u];
            sumval[u]+=sumval[v]+sumsiz[v]*val[u];
            sumsiz[u]+=sumsiz[v];
        }
    }
}
int main(){
    register int i;
    BCC=n=read();m=read();
    for(i=1;i<=m;i++){
        int x=read(),y=read();
        E[0].add(x,y);E[0].add(y,x);
    } 
    for(i=1;i<=n;i++)
        if(!dfn[i]){
        pre(i,0);
        BCC++;while(top)ADD(sta[top]),top--;
        }
    for(i=1;i<=n;i++)
        if(!vis[i])
        dfs(i,0);
    cout<<ans*2;
    return 0;
}

SDOI2018战略游戏

solution:贡献就是虚树上每条边上圆点的个数和。

CF487 E. Tourists

题目链接

solution:带修改圆方树。我们设方点为周围一圈圆点的最小权值，即该点双中的最小权值，然后要求的就是圆方树上两个圆点间的最小权值，这个可以树剖实现。带修改的实现很巧妙，因为如果修改一个圆点就暴力更新周围一圈方点显然复杂度是不对的，我们使每个方点只维护其儿子圆点，不维护父亲圆点，当查询两个圆点的lca是方点的时候直接特判加上父亲圆点即可，这样修改圆点只用修改父亲方点的权值。

当时脑子一抽：我要维护一个数据结构，支持动态插入、删除、查询集合内最小值，动态开点权值线段树！后来发现这tm就是个堆(这种错误有可能会要了老命)，最后为了方便还是写了multiset。

code：

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<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=410000;
struct Edge{
    struct edge{
        int to,next;
    }e[N];
    int head[N],tot;
    void add(int x,int y){
        e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
    }
}E[2];
int n,m,Q,w[N],BCC,dfn[N],low[N],t,sta[N],Top;
void ADD(int u){
    E[1].add(u,BCC);E[1].add(BCC,u);
}
void pre1(int u,int fa){
    low[u]=dfn[u]=++t;sta[++Top]=u;
    for(int i=E[0].head[u];i;i=E[0].e[i].next){
        int v=E[0].e[i].to;
        if(v!=fa){
            if(!dfn[v]){
                pre1(v,u);low[u]=min(low[u],low[v]);
                if(low[v]>=dfn[u]){			
                    BCC++;ADD(u);while(sta[Top]!=v)ADD(sta[Top--]);
                    ADD(sta[Top--]);
                }
            }
            else low[u]=min(low[u],dfn[v]);
        }
    }
}
multiset<int> s[N];
multiset<int>::iterator it;
int Fa[N],siz[N],cnt,deep[N],son[N],top[N],seg[N],a[N];
void pre2(int u,int fa){
//	cerr<<u<<' '<<fa<<'\n';
    Fa[u]=fa;
    deep[u]=deep[fa]+1;
    siz[u]=1;
    for(int i=E[1].head[u];i;i=E[1].e[i].next){
        int v=E[1].e[i].to;
        if(v==fa)continue;
        pre2(v,u);
        if(u>n)s[u].insert(w[v]);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
    if(u>n)w[u]=*s[u].begin();
}
void pre3(int u,int topnow){
    top[u]=topnow;
    a[++cnt]=w[u];
    seg[u]=cnt;
    if(son[u])pre3(son[u],topnow);
    for(int i=E[1].head[u];i;i=E[1].e[i].next){
        int v=E[1].e[i].to;
        if(v!=Fa[u]&&v!=son[u])pre3(v,v);
    }
}
#define ls id<<1
#define rs id<<1|1
#define mid ((l+r)>>1)
int mina[N<<2];
void up(int id){
    mina[id]=min(mina[ls],mina[rs]);
}
void build(int l,int r,int id){
    if(l==r){
        mina[id]=a[l];
        return;
    }
    build(l,mid,ls);
    build(mid+1,r,rs);
    up(id);
}
void change(int l,int r,int x,int z,int id){
    if(l==r){
        mina[id]=z;
        return;
    }
    if(x<=mid)change(l,mid,x,z,ls);
    else change(mid+1,r,x,z,rs);
    up(id);
}
int query(int l,int r,int x,int y,int id){
    if(l>=x&&r<=y)return mina[id];
    int ans=2147483647;
    if(x<=mid)ans=min(ans,query(l,mid,x,y,ls));
    if(y>mid)ans=min(ans,query(mid+1,r,x,y,rs));
    return ans;
}
void Query(int x,int y){
    int ans=2147483647;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        ans=min(ans,query(1,cnt,seg[top[x]],seg[x],1));
        x=Fa[top[x]];
    }
    if(deep[x]<deep[y])swap(x,y);
    ans=min(ans,query(1,cnt,seg[y],seg[x],1));
    if(y>n)ans=min(ans,query(1,cnt,seg[Fa[y]],seg[Fa[y]],1));
    cout<<ans<<'\n';
}
void Change(int x,int y){
    if(Fa[x]){
        it=s[Fa[x]].lower_bound(w[x]);
        s[Fa[x]].erase(it);
    }
    w[x]=y;
    change(1,cnt,seg[x],w[x],1);
    if(Fa[x]){
        s[Fa[x]].insert(w[x]);
        change(1,cnt,seg[Fa[x]],*s[Fa[x]].begin(),1);
    }
}
int main(){
    register int i;
    BCC=n=read();m=read();Q=read();
    for(i=1;i<=n;i++)w[i]=read();
    for(i=1;i<=m;i++){
        int x=read(),y=read();
        E[0].add(x,y);E[0].add(y,x);
    }
    
    pre1(1,0);
    BCC++;while(Top)ADD(sta[Top--]);
    pre2(1,0);
    pre3(1,1);
    memset(mina,127,sizeof(mina));
    build(1,cnt,1);
    while(Q--){
        char opt;cin>>opt;int x=read(),y=read();
        if(opt=='A')Query(x,y);
        else Change(x,y);
    }
    return 0;
}

HNOI2016网络

题目链接

solution:首先可能会被线段树分治误导，但是这里我们是可以处理删除的，所以不要惯性思维，老是看见个"某个限制有持续时间"就想线段树分治。考虑答案是具有二分性的，"至少有一条>=mid的边不经过x"="不是所有>=mid的边都经过x"。然后发现这个东西是可以整体二分的，按时间加>=mid的边，然后每次查询是否所有边都经过x，是的话扔左边，否则扔右边。这里要用到链上加转单点加的trick，这样复杂度就是O(nlog^2n)。

code:

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
static char buf[100000],*pa,*pd;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=410000;
struct edge{
    int to,next;
}e[N];
int head[N],tot;
void add(int x,int y){
    e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
}
struct node{
    int opt,x,y,w,id;
}q[N],q1[N],q2[N];
int n,m,cnt,siz[N],dfn[N],Fa[N],deep[N],ST[N][21],lg[N],id[N][21],oula[N],oulacnt;
void pre(int u,int fa){
    deep[u]=deep[fa]+1;
    Fa[u]=fa;
    oula[u]=++oulacnt;
    ST[oulacnt][0]=deep[u];
    id[oulacnt][0]=u;
    dfn[u]=++cnt;siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa){
            pre(e[i].to,u),siz[u]+=siz[e[i].to];
            ST[++oulacnt][0]=deep[u];
            id[oulacnt][0]=u;		
        }
}
void build(){
    register int i,j;
    for(i=2;i<=oulacnt;i++)lg[i]=lg[i>>1]+1;
    for(j=1;j<=lg[oulacnt];j++)
        for(i=1;i+(1<<j)-1<=oulacnt;i++)
            if(ST[i][j-1]<=ST[i+(1<<(j-1))][j-1])ST[i][j]=ST[i][j-1],id[i][j]=id[i][j-1];
            else ST[i][j]=ST[i+(1<<(j-1))][j-1],id[i][j]=id[i+(1<<(j-1))][j-1];
}
int lca(int x,int y){
    x=oula[x];y=oula[y];
    if(x>y)swap(x,y);
    int len=lg[y-x+1];
    if(ST[x][len]<ST[y-(1<<len)+1][len])return id[x][len];
    return id[y-(1<<len)+1][len];
}
int Tree[N];
#define lowbit(x) (x&(-x))
void ADD(int x,int y){
    while(x<=n){
        Tree[x]+=y;
        x+=lowbit(x);
    }
}
int query(int x){
    int ans=0;
    while(x){
        ans+=Tree[x];
        x-=lowbit(x);
    }
    return ans;
}
const int INF=1e9;
int ans[N];
void up(int x,int y){
    if(!x)return;
    ADD(dfn[x],y);
}
int Query(int u){
    return query(dfn[u]+siz[u]-1)-query(dfn[u]-1);
} 
void solve(int l,int r,int L,int R){
    if(L>R)return;
    int mid=(l+r)>>1;register int i;
    if(l==r){
        for(i=L;i<=R;i++)
            if(q[i].opt==2)ans[q[i].id]=l;
        return;
    }
    int cnt1=0,cnt2=0,link=0;
    for(i=L;i<=R;i++){
        if(q[i].opt==0){
            if(q[i].w<=mid){
                q1[++cnt1]=q[i];
                continue;
            }
            q2[++cnt2]=q[i];
            up(q[i].x,1);
            up(q[i].y,1);
            int Lca=lca(q[i].x,q[i].y);
            up(Lca,-1);
            up(Fa[Lca],-1);
            link++;
        }
        else if(q[i].opt==1){
            if(q[i].w<=mid){
                q1[++cnt1]=q[i];
                continue;
            }
            q2[++cnt2]=q[i];
            up(q[i].x,-1);
            up(q[i].y,-1);
            int Lca=lca(q[i].x,q[i].y);
            up(Lca,1);
            up(Fa[Lca],1);
            link--;
        }
        else{
            if(Query(q[i].x)!=link)q2[++cnt2]=q[i];
            else q1[++cnt1]=q[i];
        }
    }
    for(i=L;i<=R;i++){
        if(q[i].opt==0){
            if(q[i].w<=mid)continue;
            up(q[i].x,-1);
            up(q[i].y,-1);
            int Lca=lca(q[i].x,q[i].y);
            up(Lca,1);
            up(Fa[Lca],1);
        }
        else if(q[i].opt==1){
            if(q[i].w<=mid)continue;
            up(q[i].x,1);
            up(q[i].y,1);
            int Lca=lca(q[i].x,q[i].y);
            up(Lca,-1);
            up(Fa[Lca],-1);
        }
    }
    for(i=1;i<=cnt1;i++)q[L+i-1]=q1[i];
    for(i=1;i<=cnt2;i++)q[L+cnt1+i-1]=q2[i];
    solve(l,mid,L,L+cnt1-1);
    solve(mid+1,r,L+cnt1,R);
}
int main(){
    register int i;
    n=read();m=read();
    for(i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    pre(1,0);build();cnt=0;
    int qcnt=0;
    for(i=1;i<=m;i++){
        int opt=read();
        if(opt==0){
            int x=read(),y=read(),w=read();
            q[++cnt]=(node){0,x,y,w,0};
        }
        else if(opt==1){
            int t=read();
            q[++cnt]=q[t];q[cnt].opt=1;
        }
        else{
            int x=read();
            q[++cnt]=(node){2,x,0,0,++qcnt};
        }
    }
    solve(-1,INF,1,cnt);
    for(i=1;i<=qcnt;i++)cout<<ans[i]<<'\n';
    return 0;
}

SDOI2013森林

题目链接

soluiton:讲题现场都能想到的题就不写了吧，就是暴力的启发式合并重构主席树即可，除了码没什么价值。

PKUSC2019村庄

solution:讲题时候猜测了一下就是隔板间逆序对个数，那么先暴力扫求出n块板还在的时候的答案，每次拆除隔板直接线段树合并即可。

BZOJ3451Normal

权限题。

solution:首先各点地位相同，把复杂度摊到每个点上，就是每个点期望的点分树祖先个数，又可以拆成\sum{\text{v是u的祖先的概率}}，而这个概率就是\frac{1}{dis(u,v)}，即u->v这条有向路径上点的个数分之一，相当于在点分这条路径时，如果直接选中重心为v，那么v是u的祖先，否则不是。然后问题变成求长分别为1-n的路径数量。

考虑点分治，将自己的深度数组FFT卷一下就是经过该点的有向路径的多项式，但是其中有些不是简单路径，是不合法的，这些都是来自同一颗子树中的两项卷了起来，所以在容斥掉子树卷积后的数组即可。因为多项式次数不会超过点siz的两倍，所以复杂度是O(nlog^2n)的。

code:

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<complex>
#define comp complex<double>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=810000,INF=2147483647;
struct edge{
    int to,next;
}e[N];
int head[N],tot;
void add(int x,int y){
    e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
}
int n,vis[N],root,siz[N],allsiz,maxson[N];
void getsiz(int u,int fa){
    allsiz++;
    for(int i=head[u];i;i=e[i].next)
        if(!vis[e[i].to]&&e[i].to!=fa)
            getsiz(e[i].to,u);
}
void getroot(int u,int fa){
    siz[u]=1;maxson[u]=0;
    for(int i=head[u];i;i=e[i].next)
        if(!vis[e[i].to]&&e[i].to!=fa){
            getroot(e[i].to,u);
            siz[u]+=siz[e[i].to];
            maxson[u]=max(maxson[u],siz[e[i].to]);
        }
    maxson[u]=max(maxson[u],allsiz-siz[u]);
    if(maxson[u]<maxson[root])root=u;
}
int ans[N],tong1[N],tong2[N],deep[N];
void gettong(int u,int fa){
    deep[u]=deep[fa]+1;
    tong2[deep[u]]++;
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa&&!vis[e[i].to])
            gettong(e[i].to,u),siz[u]+=siz[e[i].to];
}
int bt[N],limit=1,l;
comp a[N];
const double pi=acos(-1);
void FFT(comp *A,int kind){
    register int i,j,k,mid,r;
    for(i=0;i<limit;i++)if(i<bt[i])swap(A[i],A[bt[i]]);
    for(mid=1;mid<limit;mid<<=1){
        comp W(cos(pi/mid),sin(pi/mid)*kind);
        for(r=mid<<1,j=0;j<limit;j+=r){
            comp w(1,0);
            for(k=0;k<mid;k++,w*=W){
                comp x=A[j+k],y=w*A[j+k+mid];
                A[j+k]=x+y;
                A[j+k+mid]=x-y;
            }
        }
    }
}
void mul(int *A,int len){
    register int i;
    limit=1;l=0;
    while(limit<=2*len)limit<<=1,l++;
    for(i=0;i<limit;i++)a[i]=A[i];	
    for(i=0;i<limit;i++)bt[i]=(bt[i>>1]>>1)|(i&1)<<(l-1);
    FFT(a,1);
    for(i=0;i<limit;i++)a[i]*=a[i];
    FFT(a,-1);
    for(i=0;i<=2*len;i++)A[i]=(int)(a[i].real()/limit+0.5);
}
void solve(int u){
    vis[u]=1;
    register int i,j;
    int All=1;
    
    tong1[0]=1;
    deep[u]=0;
    for(i=head[u];i;i=e[i].next)
        if(!vis[e[i].to]){
            gettong(e[i].to,u);
            All+=siz[e[i].to];
            for(j=1;j<=siz[e[i].to];j++)tong1[j]+=tong2[j];
            mul(tong2,siz[e[i].to]);
            for(j=1;j<=siz[e[i].to]*2;j++)ans[j]-=tong2[j],tong2[j]=0;
        }
    mul(tong1,All);
    for(j=0;j<=All;j++)ans[j]+=tong1[j];
    for(i=0;i<=All;i++)tong1[i]=0;
    
    for(i=head[u];i;i=e[i].next)
        if(!vis[e[i].to]){
            allsiz=0;getsiz(e[i].to,u);
            root=0;getroot(e[i].to,u);
            solve(root);
        }
}
int main(){
    register int i;
    n=read();
    maxson[0]=INF;
    for(i=1;i<n;i++){
        int x=read()+1,y=read()+1;
        add(x,y);add(y,x);
    }
    getsiz(1,0);
    getroot(1,0);
    solve(root);
    double lastans=0;
    for(i=0;i<n;i++)lastans+=1.00*ans[i]/((double)i+1);
    printf("%.4lf",lastans);
    return 0;
}
//少有的一遍过，开心.jpg

WC2018通道

solution:首先考虑边分第一颗树，对第二颗树建虚树，设w(u,v)=D(x)+D(y)+deep_2(x)+deep_2(y)-2lca_2(x,y)-dis_3(x,y)，其中D是到边分的边的距离，dfs第二颗树的虚树，那么相当于枚举lca前面都被控制了，相当于给第三颗树上每个点挂了一条边，权值为D(u)+deep2(x)，然后枚举lca，对左右子树黑白染色，询问第三颗树上的最远异色点对。

这里有个结论：两个点树上集合并后的直径必定是原先两个点集直径上的四个点取其中两个。

然后就是维护虚树上每个点子树内的直径点对，每次合并就分四种情况讨论就可以了(交叉相配)。

code:

咕咕咕。

PKUWC2018 Minimax

solution:首先权值是可以离散的，那个D^2也可以直接求D，所以我们要做的就是统计根取每个值得概率。线段树维护以排名为下标的概率，转移如下

P(root,x)=P(ls,x)*(p[i]*\sum_{val(y)<x}P(rs,y)+(1-p[i])*\sum_{val(y)>x}P(rs,y))

每次线段树合并即可，当遇到只有某一边的节点时，说明在另一边比它们大的集合和比它们小的集合

都是一样的，即后面那一坨是一样的，区间乘法即可，依靠前序遍历记下比这些数数小的集合，最后扫一遍根的线段树统计答案。

另外对于这种不好调试的概率取模，可以通过查询sum(P)是否为1检验自己是否写错了。

还有就是线段树合并在有标记的时候要先下传标记.

code:

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=410000,P=998244353;
int n,vis[N],val[N],p[N],b[N],cnt,L[N],R[N];
int quickpow(int a,int b){
    int ans=1,base=a;
    while(b){
        if(b&1)(ans*=base)%=P;
        (base*=base)%=P;
        b>>=1;
    }
    return ans;
}
int inv(int x){
    return quickpow(x,P-2);
}
int Ls[N<<5],Rs[N<<5],mul[N<<5],sum[N<<5],T[N];
#define ls Ls[id]
#define rs Rs[id]
#define mid ((l+r)>>1)
void up(int id){
    sum[id]=(sum[ls]+sum[rs])%P;
}
void down(int id){
    sum[ls]=sum[ls]*mul[id]%P;
    sum[rs]=sum[rs]*mul[id]%P;
    mul[ls]=mul[ls]*mul[id]%P;
    mul[rs]=mul[rs]*mul[id]%P;
    mul[id]=1;
}
int node;
int insert(int l,int r,int x,int id){
    if(!id)id=++node;mul[id]=1;
    if(l==r){
        sum[id]=1;
        return id;
    }
    if(x<=mid)ls=insert(l,mid,x,ls);
    else rs=insert(mid+1,r,x,rs);
    up(id);
    return id;
}
int sum1,sum2,all1,all2;
int merge(int x,int y,int K){
    if(!x){
        (sum2+=sum[y])%=P;
        (sum[y]*=(K*sum1%P+(1ll-K+P)%P*(all1-sum1+P))%P)%=P;
        (mul[y]*=(K*sum1%P+(1ll-K+P)%P*(all1-sum1+P))%P)%=P;
        return y;	
    }
    if(!y){ 
        (sum1+=sum[x])%=P;
        (sum[x]*=(K*sum2%P+(1ll-K+P)%P*(all2-sum2+P))%P)%=P;
        (mul[x]*=(K*sum2%P+(1ll-K+P)%P*(all2-sum2+P))%P)%=P;
        return x;
    }
    down(x);down(y);
    Ls[x]=merge(Ls[x],Ls[y],K);
    Rs[x]=merge(Rs[x],Rs[y],K);
    up(x);
    return x;
}
void dfs(int u){
    if((!L[u])&&(!R[u]))return;
    if(L[u])dfs(L[u]);
    if(R[u])dfs(R[u]);
    if(!L[u]||!R[u])T[u]=T[L[u]]+T[R[u]];
    else{
        sum1=sum2=0;all1=sum[T[L[u]]];all2=sum[T[R[u]]];
        T[u]=merge(T[L[u]],T[R[u]],p[u]);
    //	cerr<<u<<' '<<sum[T[u]]<<'\n';
    }
    
}
int query(int l,int r,int x,int id){
    if(l==r)return sum[id];
    down(id);
    if(x<=mid)return query(l,mid,x,ls);
    else return query(mid+1,r,x,rs);
}
void getans(){
    int ans=0;
    for(int i=1;i<=cnt;i++){
        int D=query(1,cnt,i,T[1]);//cerr<<'*'<<D<<'\n';
        (ans+=D*D%P*i%P*b[i]%P)%=P;
    }
    cout<<ans<<'\n';
}
signed main(){
    register int i;
    n=read();
    for(i=1;i<=n;i++){
        int x=read();
        if(!x)continue;
        if(!vis[x])L[x]=i,vis[x]=1;
        else R[x]=i;
    }
    for(i=1;i<=n;i++)
        if(vis[i])p[i]=read()*inv(10000)%P;
        else val[i]=read(),b[++cnt]=val[i];
    sort(b+1,b+1+cnt);
    for(i=1;i<=n;i++)if(val[i])val[i]=lower_bound(b+1,b+1+cnt,val[i])-b,T[i]=insert(1,cnt,val[i],T[i]);
    dfs(1);	
    getans();	
    return 0;
}

杂题

共价大爷游长沙

题目链接

solution:神仙题目，有一个神奇的想法，给每条路径异或一个随机权值，若某条边的权值等于在场所有权值的异或和则它是关键的。为什么是异或而不是其他运算?因为方便修改，这种将树上路径“别”过来的操作大多都是异或，并且对于3操作，异或两次就是撤销。如果新加边(x,y)，减边(u,v)，若(u,v)权值是w，那么我们将新图中(x,y)的路径异或w，等价于把经过(u,v)的路径都别过来了。于是我们要做的就是边转点，用LCT支持路径异或，单点求值即可。

code:

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<ctime>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=2100000;
struct node{
    int son[2],valtag,val,tag,fa;
}a[N];
#define ls(x) a[x].son[0]
#define rs(x) a[x].son[1]
#define fa(x) a[x].fa
void rev(int x){swap(ls(x),rs(x));} 
int which(int x){return rs(fa(x))==x;}
int nroot(int x){return ls(fa(x))==x||rs(fa(x))==x;}
void down(int x){
    if(a[x].tag){rev(ls(x));rev(rs(x));a[ls(x)].tag^=1;a[rs(x)].tag^=1;a[x].tag=0;}
    a[ls(x)].valtag^=a[x].valtag;a[rs(x)].valtag^=a[x].valtag;
    a[ls(x)].val^=a[x].valtag;a[rs(x)].val^=a[x].valtag;
    a[x].valtag=0;
}
void downall(int x){if(nroot(x))downall(fa(x));down(x);}
void rotate(int x){
    int y=fa(x),z=fa(y),k=which(x);
    a[y].son[k]=a[x].son[k^1];a[x].son[k^1]=y;if(nroot(y))a[z].son[which(y)]=x;
    fa(x)=z;fa(y)=x;if(a[y].son[k])fa(a[y].son[k])=y;
}
void splay(int x){
    for(downall(x);nroot(x);rotate(x)){
        int y=fa(x);
        if(nroot(y))rotate(which(x)==which(y)?y:x);
    }
}
void access(int x){for(int y=0;x;y=x,x=fa(x)){splay(x);rs(x)=y;}}
void makeroot(int x){access(x);splay(x);rev(x);a[x].tag^=1;}
int n,m,cnt;
map<pair<int,int>,int>id;
void link(int x,int y){makeroot(x);access(y);splay(y);fa(x)=y;}
void cut(int x,int y){makeroot(x);access(y);splay(y);ls(y)=fa(x)=0;}
void split(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
}
void Link(int x,int y){
    id[make_pair(x,y)]=id[make_pair(y,x)]=++cnt;
    link(x,cnt);link(y,cnt);
}
void Cut(int x,int y){
    int u=id[make_pair(x,y)];
    id[make_pair(x,y)]=id[make_pair(y,x)]=0;
    cut(u,x);cut(u,y);
}
int all;
struct edge{
    int x,y,w;
}d[N];
int cntd;
int main(){
    register int i;
    srand(time(0));//有个恶心人的hack默认种子
    int tp=read();
    cnt=n=read();m=read();
    for(i=1;i<n;i++){
        int x=read(),y=read();
        Link(x,y);
    }	
    while(m--){
        int opt=read();
        switch(opt){
            case 1:{
                int u1=read(),v1=read(),u2=read(),v2=read();
                int od=id[make_pair(u1,v1)];
                access(od);splay(od);
                int oval=a[od].val;
                Cut(u1,v1);
                Link(u2,v2);
                split(u1,v1);
                a[v1].val^=oval;a[v1].valtag^=oval;
                break;
            }
            case 2:{
                int x=read(),y=read();
                split(x,y);
                int nv=rand()*rand();
                a[y].val^=nv,a[y].valtag^=nv;all^=nv;	
                d[++cntd]=(edge){x,y,nv};			
                break;
            }
            case 3:{
                int x=read();
                split(d[x].x,d[x].y);
                a[d[x].y].val^=d[x].w;
                a[d[x].y].valtag^=d[x].w;	
                all^=d[x].w;	
                break;
            }
            case 4:{
                int x=read(),y=read();
                int u=id[make_pair(x,y)];
                access(u);splay(u);
                if(a[u].val==all)cout<<"YES"<<'\n';
                else cout<<"NO"<<'\n';
                break;
            }
        }
    }
    return 0;
}
/*
0
2 4
1 2
2 1 1
2 1 2
1 1 2 1 2
4 1 2
*/

树剖/LCT维护动态DP

树剖：

每个元素等于轻儿子矩阵乘自己矩阵，维护重链矩阵积，每次修改的时候进行：改重链、找它作为轻链的位置（链顶）、修改父亲矩阵、改父亲重链，反复进行。记录链底，查询就查询根所在重链。复杂度O(nlog^2 n)

code:

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
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=410000;
#define int long long
struct edge{
    int next,to;
}e[N];
int head[N],tot;
void add(int x,int y){
    e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
}
int n,m,cnt,seg[N],rev[N],bot[N],top[N],fa[N],son[N],siz[N],val[N],f[N][2];
struct mat{
    int a[2][2];
    int *operator [](int x){return a[x];}
}dfn[N],sum[N];
mat operator * (mat x,mat y){
    mat ans;
    ans[0][0]=max(x[0][0]+y[0][0],x[0][1]+y[1][0]);
    ans[0][1]=max(x[0][0]+y[0][1],x[0][1]+y[1][1]);
    ans[1][0]=max(x[1][0]+y[0][0],x[1][1]+y[1][0]);
    ans[1][1]=max(x[1][0]+y[0][1],x[1][1]+y[1][1]);
    return ans;
}

void dfs1(int u,int fath){
    fa[u]=fath;
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fath){
            dfs1(e[i].to,u);
            siz[u]+=siz[e[i].to];
            if(siz[e[i].to]>siz[son[u]])son[u]=e[i].to;
        }
}
void dfs2(int u,int topnow){
    seg[u]=++cnt;
    rev[cnt]=u;
    top[u]=topnow;
    bot[topnow]=cnt;
    if(son[u])dfs2(son[u],topnow);
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa[u]&&e[i].to!=son[u])
            dfs2(e[i].to,e[i].to);
}

void dfs(int u,int fath){
    f[u][1]+=val[u];
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fath){
            int v=e[i].to;
            dfs(v,u);
            f[u][0]+=max(f[v][0],f[v][1]);
            f[u][1]+=f[v][0];
        }
}
const int INF=1e9;
#define ls id<<1
#define rs id<<1|1
#define mid ((l+r)>>1)
void up(int id){
    sum[id]=sum[ls]*sum[rs];
}
void build(int l,int r,int id){
    if(l==r){
        int u=rev[l];
        sum[id][1][0]=val[u];
        for(int i=head[u];i;i=e[i].next)
            if(e[i].to!=fa[u]&&e[i].to!=son[u])
                sum[id][0][0]+=max(f[e[i].to][0],f[e[i].to][1]),sum[id][1][0]+=f[e[i].to][0];
        sum[id][0][1]=sum[id][0][0];
        dfn[l]=sum[id];
        return;
    }
    build(l,mid,ls);
    build(mid+1,r,rs);
    up(id);
}
void change(int l,int r,int x,int id){
    if(l==r){
        sum[id]=dfn[l];
        return;
    }
    if(x<=mid)change(l,mid,x,ls);
    else change(mid+1,r,x,rs);
    up(id);
}
mat query(int l,int r,int x,int y,int id){
    if(l>=x&&r<=y)return sum[id];
    if(y<=mid)return query(l,mid,x,y,ls);
    if(x>mid)return query(mid+1,r,x,y,rs);
    return query(l,mid,x,y,ls)*query(mid+1,r,x,y,rs);
}
void Change(int x,int y){
    dfn[seg[x]][1][0]+=y-val[x];val[x]=y;
    while(x){
        mat od=query(1,n,seg[top[x]],bot[top[x]],1);
        change(1,n,seg[x],1);
        mat nw=query(1,n,seg[top[x]],bot[top[x]],1);
        x=fa[top[x]];
        if(x){
            dfn[seg[x]][0][0]+=max(nw[0][0],nw[1][0])-max(od[0][0],od[1][0]);
            dfn[seg[x]][0][1]=dfn[seg[x]][0][0];
            dfn[seg[x]][1][0]+=nw[0][0]-od[0][0]; 
        }
    } 
}
signed main(){
    n=read();m=read();
    register int i;
    for(i=1;i<=n;i++)val[i]=read();
    for(i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    dfs(1,0);
    build(1,n,1);
    while(m--){
        int x=read(),y=read();
        Change(x,y);
        mat ans=query(1,n,1,bot[1],1);
        cout<<max(ans[0][0],ans[1][0])<<'\n';
    }
    return 0;
}
LCT：

每个元素等于虚儿子矩阵乘自己矩阵，修改就是在access的时候把新的虚儿子加上，新的实儿子减去。查询就是把原树的根转到根，然后查询根在的实链的矩阵积（就是那颗splay的根的矩阵）。这里特别要注意的是因为转移是深度小的主动合并深度大的，所以要先matrix(ls)*matrix(u)，然后再matrix(u)*matrix(rs)。

code:

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=210000;
struct mat{
    int matrix[2][2];
    int *operator [] (int x){return matrix[x];}
    mat(){matrix[0][0]=matrix[0][1]=matrix[1][0]=matrix[1][1]=-1e9;}
};
struct edge{
    int to,next,w;
}e[N];
int head[N],tot;
void add(int x,int y){
    e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
}
struct node{
    mat f,g;
    int son[2],fa,tag;
}a[N];
#define fa(x) a[x].fa
#define ls(x) a[x].son[0]
#define rs(x) a[x].son[1]
mat operator * (mat a,mat b){
    register int i,j,k;
    mat ans;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            for(k=0;k<2;k++)	
                ans[i][j]=max(a[i][k]+b[k][j],ans[i][j]);
    return ans;
}
void up(int x){
    a[x].f=a[x].g;
    if(ls(x))a[x].f=a[ls(x)].f*a[x].f;
    if(rs(x))a[x].f=a[x].f*a[rs(x)].f;
}
void rev(int x){swap(ls(x),rs(x));}
void down(int x){if(a[x].tag){a[ls(x)].tag^=1;a[rs(x)].tag^=1;rev(ls(x));rev(rs(x));a[x].tag=0;}}
int nroot(int x){return rs(fa(x))==x||ls(fa(x))==x;}
int which(int x){return rs(fa(x))==x;}
void downall(int x){
    if(nroot(x))downall(fa(x));
    down(x);
}
void rotate(int x){
    int y=fa(x),z=fa(y),k=which(x);
    a[y].son[k]=a[x].son[k^1];a[x].son[k^1]=y;if(nroot(y))a[z].son[which(y)]=x;
    fa(x)=z;fa(y)=x;if(a[y].son[k])fa(a[y].son[k])=y;
    up(y);up(x);
}
void splay(int x){
    for(downall(x);nroot(x);rotate(x)){
        int y=fa(x);
        if(nroot(y))rotate(which(x)==which(y)?y:x);
    }
}
void access(int x){
    for(int y=0;x;y=x,x=fa(x)){
        splay(x);
        if(y){
            a[x].g[0][0]-=max(a[y].f[0][0],a[y].f[1][0]);
            a[x].g[0][1]=a[x].g[0][0];
            a[x].g[1][0]-=a[y].f[0][0];
        }
        if(rs(x)){
            a[x].g[0][0]+=max(a[rs(x)].f[0][0],a[rs(x)].f[1][0]);
            a[x].g[0][1]=a[x].g[0][0];
            a[x].g[1][0]+=a[rs(x)].f[0][0];
        }
        rs(x)=y;up(x);
    }
}
int n,m,val[N],f[N][2];
void dfs(int u,int fa){
    f[u][1]=val[u];
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa){
            dfs(e[i].to,u);
            f[u][1]+=f[e[i].to][0];
            f[u][0]+=max(f[e[i].to][0],f[e[i].to][1]);
        }
    a[u].f[0][0]=a[u].f[0][1]=f[u][0];
    a[u].f[1][0]=f[u][1];
    a[u].g=a[u].f;
    a[u].fa=fa;
}
int main(){
    register int i;
    n=read();m=read();
    for(i=1;i<=n;i++)val[i]=read();
    for(i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    dfs(1,0);
    while(m--){
        int x=read(),y=read();
        access(x);
        splay(x);
        a[x].g[1][0]+=y-val[x];val[x]=y;
        up(x);
        splay(1);
        cout<<max(a[1].f[0][0],a[1].f[1][0])<<'\n';
    }
    return 0;
}

NOI2014魔法森林

题目链接

solution:权值按第一维排序，LCT动态维护第二维最小生成树，边权转点权，维护链上最值即可。

水管局长

题目链接

solution:离线询问，倒序变加边，维护最小生成树。

大融合

题目链接

solution:LCT维护子树信息。

0%