这道题是标准的树上带修改莫队. 兔哥称之为 "莫队的集大成者".
先说一下树上莫队吧. 树上莫队就是把莫队搬到了树上, 它的算法仍然是通过对树进行分块, 使得各个元素属于一个块, 之后像普通的莫队一样, 按照左右端点所属的块排序. 至于树上分块的做法, 直接看这篇博客的上一篇 https://www.cnblogs.com/captain1/p/10105468.html 就好了.
然后我们说一下具体的做法. 首先还是先把其他东西处理好, lca 可以使用各种方法求一下. 然后直接开干, 基本的想法和普通莫队很相似, 但是实现起来要复杂很多. 普通序列中, 很自然会把指针向左右移动并且简单的维护, 但是树上不行.
实现树上维护的最好的方法是开一个 \(vis\) 数组记录一下当前节点是否被走过. 然后在走过的时候依次取反. 具体的, 我们从当前二元组 \((cur_u,cur_v)\), 走到下一个二元组 \((tar_u,tar_v)\) 的时候, 我们只需要把路径 \((cur_u,tar_u)\) 和路径 \((cur_v,tar_v)\) 上所有的节点走过一次之后取反就可以了. 这个我们可以画图理解一下, 具体的证明摘抄可以点击这里
这样就可以开始我们的操作了. 在每次进行反转的时候, 先减去对应的权值, 之后再加上对应的权值. 树上的行走方法是先找 lca, 之后直接暴力跳父亲反转路径上节点. 然后这道题带修改, 那么我们仿照带修改莫队, 通过时间线修改就可以了.
然后注意的是 lca 那个点, 只有在正式查询的时候才会把它反转一次计算答案, 之后再反转回去. 因为在行走过程中, 每次 lca 都必然被修改两次, 所以我们把它特殊处理就好了.
之后基本就好了. 要注意的是这题的变量非常多, 千万不要像我一样变量名打错然后 de 不出来...... 我用的 ST 表求 lca.
看一下代码.
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<iostream>
- #include<cmath>
- #include<set>
- #include<vector>
- #include<map>
- #include<queue>
- #define rep(i,a,n) for(int i = a;i <= n;i++)
- #define per(i,n,a) for(int i = n;i>= a;i--)
- #define enter putchar('\n')
- #define fr friend inline
- #define y1 poj
- #define mp make_pair
- #define fi first
- #define sc second
- #define pb push_back
- #define I puts("Oops")
- using namespace std;
- typedef long long ll;
- const int M = 100005;
- const int N = 1000005;
- const int INF = 1000000009;
- const double eps = 1e-7;
- int read()
- {
- int ans = 0,op = 1;char ch = getchar();
- while(ch <'0' || ch> '9') {if(ch == '-') op = -1;ch = getchar();}
- while(ch>= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();
- return ans * op;
- }
- int n,m,st[22][M<<2],Q,x,y,c[M],op,blo[M],head[M],ecnt,dep[M],dfn[M<<1],B,sta[M],top,pos[M];
- int idx,lg[M<<1],cnt,pl,pr,cpos[M],cval[M],ctim[M],cntc,cntq,fa[M],cur,walk[M],pre[M];
- ll ans[M],w[M],v[M],res;
- bool vis[M];
- struct ask
- {
- int l,r,tim,id;
- bool operator <(const ask &g) const
- {
- if(blo[l] != blo[g.l]) return blo[l] < blo[g.l];
- if(blo[r] != blo[g.r]) return blo[r] < blo[g.r];
- return tim < g.tim;
- }
- }q[M];
- struct edge
- {
- int next,to,from;
- }e[M<<1];
- void add(int x,int y)
- {
- e[++ecnt].to = y;
- e[ecnt].next = head[x];
- head[x] = ecnt;
- }
- int Min(int p,int q) {return (dep[p] < dep[q]) ? p : q;}
- void dfs(int x,int f)
- {
- dep[x] = dep[f] + 1,dfn[++idx] = x,pos[x] = idx,fa[x] = f;
- int cur = top;
- for(int i = head[x];i;i = e[i].next)
- {
- if(e[i].to == f) continue;
- dfs(e[i].to,x),dfn[++idx] = x;
- if(top - cur>= B) {cnt++;while(top> cur) blo[sta[top--]] = cnt;}
- }
- sta[++top] = x;
- }
- void build()
- {
- lg[0] = -1;
- rep(i,1,idx) st[0][i] = dfn[i],lg[i] = lg[i>>1] + 1;
- rep(j,1,lg[idx])
- rep(i,1,idx)
- {
- if(i + (1 <<j) - 1> idx) break;
- st[j][i] = Min(st[j-1][i],st[j-1][i + (1 <<(j-1))]);
- }
- }
- int lca(int p,int q)
- {
- int kl = pos[p],kr = pos[q];
- if(kl> kr) swap(kl,kr);
- int k = lg[kr - kl + 1];
- return Min(st[k][kl],st[k][kr - (1 <<k) + 1]);
- }
- void rev(int x)
- {
- if(vis[x]) res -= w[walk[c[x]]] * v[c[x]],walk[c[x]]--;
- else walk[c[x]]++,res += w[walk[c[x]]] * v[c[x]];
- vis[x] ^= 1;
- }
- void cadd()
- {
- bool flag = 0;
- if(vis[cpos[cur]]) flag = 1,rev(cpos[cur]);
- pre[cur] = c[cpos[cur]],c[cpos[cur]] = cval[cur];
- if(flag) rev(cpos[cur]);
- }
- void cdel()
- {
- bool flag = 0;
- if(vis[cpos[cur]]) flag = 1,rev(cpos[cur]);
- c[cpos[cur]] = pre[cur];
- if(flag) rev(cpos[cur]);
- }
- void treewalk(int p,int q)
- {
- int g = lca(p,q);
- while(p != g) rev(p),p = fa[p];
- while(q != g) rev(q),q = fa[q];
- }
- void change(int x)
- {
- while(cur < cntc && ctim[cur + 1] <= x) cur++,cadd();
- while(cur && ctim[cur]> x) cdel(),cur--;
- }
- int main()
- {
- n = read(),m = read(),Q = read(),B = 2000;
- rep(i,1,m) v[i] = read();
- rep(i,1,n) w[i] = read();
- rep(i,1,n-1) x = read(),y = read(),add(x,y),add(y,x);
- rep(i,1,n) c[i] = read();
- rep(i,1,Q)
- {
- op = read(),x = read(),y = read();
- if(!op) ctim[++cntc] = i,cpos[cntc] = x,cval[cntc] = y;
- else q[++cntq].l = x,q[cntq].r = y,q[cntq].tim = i,q[cntq].id = cntq;
- }
- dfs(1,0),build();
- while(top) blo[sta[top--]] = cnt;
- sort(q+1,q+1+cntq),pl = pr = 1;
- rep(i,1,cntq)
- {
- change(q[i].tim);
- treewalk(pl,q[i].l),pl = q[i].l,treewalk(pr,q[i].r),pr = q[i].r;
- rev(lca(pl,pr)),ans[q[i].id] = res,rev(lca(pl,pr));
- }
- rep(i,1,cntq) printf("%lld\n",ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2881325.html