题解
- 没错这题我又是水过的,水法真神奇
- 我们只用维护每个点的父亲是谁,在删变时只用将深度大的点的父亲改为自己
- 求答案时,我们从两个点暴力向上跳到最高,如果祖先相同则相乘,不然就相加
- 修改就直接改就好了
- 正解又是树链剖分
- 选一个点作为根,对每个点维护连向父亲节点那条边是否被断开,如果未断开则为1,否则为0
- 然后树链剖分维护区间和即可
代码
1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 using namespace std;
5 const int N=2e5+10;
6 int n,m,lastans,a[N],f[N];
7 void cut(int x,int y) { if (f[x]==y) f[x]=x; else f[y]=y; }
8 int work(int x,int y)
9 {
10 int u=x,v=y;
11 while (f[x]!=x) x=f[x];
12 while (f[y]!=y) y=f[y];
13 return (x==y)?a[u]*a[v]:a[u]+a[v];
14 }
15 int main()
16 {
17 scanf("%d%d",&n,&m);
18 for (int i=1;i<=n;i++) scanf("%d",&a[i]);
19 for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),f[y]=x;
20 for (int op,x,y;m;m--)
21 {
22 scanf("%d%d%d",&op,&x,&y),x^=lastans,y^=lastans;
23 if (op==1) cut(x,y);
24 if (op==2) printf("%d
",(lastans=work(x,y)));
25 if (op==3) a[x]=y;
26 }
27 }