[WC2013]糖果公园

Description

题库链接

给你一棵 $n$ 个节点，有 $m$种颜色的树。每个节点上有一个颜色。定义一条树上路径的价值为

$sum_c V_c(sum_{i=1}^{tim_c}W_i)$

其中 $V,W$已经给出， $tim_c$ 表示路径上 $c$ 颜色的节点数。

现在给出 $q$ 个操作，让你实现：

修改节点颜色；
询问树上路径的价值。

$1leq n,m,qleq 100000$

转载自Navi_Awson

如果这题出在序列上而不是在树上，很容易用莫队求解。

考虑用类似的方法，我们将树分块，采用[SCOI 2005]王室联邦的方法。

对于树上分块的复杂度和块的大小的选取可以参见ljh的博客，这里摘出了一些：

设 $block_{num}$ 为块数， $block_{size}$ 为块的大小，则有 $block_{num} imes block_{size}=n$ ，在证明中我们假设 $n,q$ 同阶。
设块对 $(block_i,block_j)$ ，易知这样的块对不会超过 $block_{size}^2$ 个。
对于块对内的操作：我们考虑总复杂度，左端点共移动至多 $O(q imes block_{size})$ ，右端点亦是。时间共移动至多 $O(block_{num}^2 imes q)$ 。故这一部分的复杂度为 $O(n imes(block_{size}+block_{num}^2))$ 。
对于块与块之间的操作，不超过 $block_{num}^2$ 次：左端第移动一次，最多 $O(n)$ ，右端点亦是如此。时间最多移动 $O(q)=O(n)$ 。故这一部分复杂度为 $O(block_{num}^2 imes n)$。
故总复杂度为 $O(n imes(block_{size}+block_{num}^2))$。
可以证明当 $block_{size}=n^{frac{2}{3}}$ 时， $block_{num}=n^{frac{1}{3}}$ ，复杂度最优，为 $O(n^{frac{5}{3}})$ 。

至于莫队的操作，就是将序列中移动左右端点变成在树上移动路径的两个端点。对于修改，我们同样是模拟时间倒流和消逝。

那么怎么去移动结点来保证提取出路径？

考虑我们树上的所有结点，实际上可以认为是 $0/1$ 状态——计入答案或者未计入答案。

考虑用类似于异或的思想来执行操作，比如：计入答案再从答案中去掉，等于异或了两次 $1$ ，就等于原来的数。假设这次的起点、终点为 $u,v$ ，上次为 $x,y$ ，那么可以对 $x$ 到 $u$ 的路径、 $v$ 到 $y$ 的路径进行一次取 $xor$ 操作。注意的是对 $lca$ 不做处理，这样就能保证每次操作之后图上打上标记的点只在 $(u,lca)$和 $(v,lca)$ 的路径上（不包括 $lca$ ）。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 typedef long long lol;
  8 struct ZYYS
  9 {
 10   int x,y,p,id;
 11 }p[100001],q[100001];
 12 struct Node
 13 {
 14   int next,to;
 15 }edge[200001];
 16 int num,head[100001],block[100001],tot,size[100001],son[100001],block_size,block_num,cnt,s[100001];
 17 int top[100001],dfn[100001],dep[100001],fa[100001],rev[100001],c[100001],n,m,Q,pre[100001],cntp,cntq;
 18 int curl,curr,curp;
 19 lol sum,v[100001],w[100001],ans[100001];
 20 bool cmp(ZYYS a,ZYYS b)
 21 {
 22   if (block[a.x]==block[b.x])
 23     {
 24       if (block[a.y]==block[b.y]) return a.id<b.id;
 25       else return block[a.y]<block[b.y];
 26     }
 27   else return block[a.x]<block[b.x];
 28 }
 29 void add(int u,int v)
 30 {
 31   num++;
 32   edge[num].next=head[u];
 33   head[u]=num;
 34   edge[num].to=v;
 35 }
 36 void dfs1(int x,int pa)
 37 {int i;
 38   int bot=tot;
 39   fa[x]=pa;
 40   size[x]=1;
 41   dep[x]=dep[pa]+1;
 42   for (i=head[x];i;i=edge[i].next)
 43     {
 44       int v=edge[i].to;
 45       if (v==pa) continue;
 46       dfs1(v,x);
 47       if (size[son[x]]<size[v]) son[x]=v;
 48       size[x]+=size[v];
 49       if (tot-bot>=block_size)
 50     {
 51       ++cnt;
 52       while (tot>bot)
 53         {
 54           block[s[tot--]]=cnt;
 55         }
 56     }
 57     }
 58   s[++tot]=x;
 59 }
 60 void dfs2(int x,int pa,int tp)
 61 {int i;
 62   top[x]=tp;
 63   dfn[x]=++tot;
 64   if (son[x]) dfs2(son[x],x,tp);
 65   for (i=head[x];i;i=edge[i].next)
 66     {
 67       int v=edge[i].to;
 68       if (v==pa||v==son[x]) continue;
 69       dfs2(v,x,v);
 70     }
 71 }
 72 int get_lca(int x,int y)
 73 {
 74   while (top[x]!=top[y])
 75     {
 76       if (dep[top[x]]<dep[top[y]]) swap(x,y);
 77       x=fa[top[x]];
 78     }
 79   if (dep[x]<dep[y]) return x;
 80   return y;
 81 }
 82 void reverse(int x)
 83 {
 84   if (rev[x]) sum-=v[c[x]]*w[s[c[x]]],s[c[x]]--;
 85   else s[c[x]]++,sum+=v[c[x]]*w[s[c[x]]];
 86   rev[x]^=1;
 87 }
 88 void update(int x,int y)
 89 {
 90   if (rev[x]) reverse(x),c[x]=y,reverse(x);
 91   else c[x]=y;
 92 }
 93 void move(int x,int y)
 94 {
 95   while (x!=y)
 96     {
 97       if (dep[x]<dep[y]) swap(x,y);
 98       reverse(x);
 99       x=fa[x];
100     }
101 }
102 int main()
103 {int i,uu,vv,opt,x,y;
104   cin>>n>>m>>Q;
105   for (i=1;i<=m;i++)
106     scanf("%lld",&v[i]);
107   for (i=1;i<=n;i++)
108     scanf("%lld",&w[i]);
109   block_size=pow(n,0.666667);
110   block_num=n/block_size;
111   for (i=1;i<n;i++)
112     {
113       scanf("%d%d",&uu,&vv);
114       add(uu,vv);add(vv,uu);
115     }
116   for (i=1;i<=n;i++)
117     {
118       scanf("%d",&c[i]);
119       pre[i]=c[i];
120     }
121   dfs1(1,0);
122   ++cnt;
123   while (tot)
124     {
125       block[s[tot--]]=cnt;
126     }
127   tot=0;
128   memset(s,0,sizeof(s));
129   dfs2(1,0,1);
130   for (i=1;i<=Q;i++)
131     {
132       scanf("%d",&opt);
133       if (opt==0)
134     {
135       scanf("%d%d",&x,&y);
136       p[++cntp]=(ZYYS){x,y,pre[x],0};
137       pre[x]=y;
138     }
139       else
140     {
141       scanf("%d%d",&x,&y);
142       q[++cntq]=(ZYYS){x,y,cntp,cntq};
143     }
144     }
145   sort(q+1,q+cntq+1,cmp);
146   curl=1;curr=1;curp=0;
147   for (i=1;i<=cntq;i++)
148     {
149       while (curp<q[i].p) {curp++;update(p[curp].x,p[curp].y);}
150       while (curp>q[i].p) {update(p[curp].x,p[curp].p);curp--;}
151       move(curl,q[i].x);curl=q[i].x;
152       move(curr,q[i].y);curr=q[i].y;
153       int lca=get_lca(curl,curr);
154       reverse(lca);
155       ans[q[i].id]=sum;
156       reverse(lca);
157     }
158   for (i=1;i<=cntq;i++)
159     {
160       printf("%lld
",ans[i]);
161     }
162 }