UOJ58 【WC2013】糖果公园

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

【问题描述】

Candyland 有一座糖果公园,公园里不仅有美丽的风景、好玩的游乐项目,还有许多免费糖果的发放点,这引来了许多贪吃的小朋友来糖果公园游玩。
糖果公园的结构十分奇特,它由 n 个游览点构成,每个游览点都有一个糖果发放处,我们可以依次将游览点编号为 1 至 n。有 n – 1 条 双向道路 连接着这些游览点,并且整个糖果公园都是 连通的 ,即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。
糖果公园所发放的糖果种类非常丰富,总共有 m 种,它们的编号依次为 1至 m。每一个糖果发放处都只发放某种特定的糖果,我们用 C i 来表示 i 号游览点的糖果。
来到公园里游玩的游客都 不喜欢走回头路 ,他们总是从某个特定的游览点出发前往另一个特定的游览点,并游览途中的景点,这条路线一定是唯一的。他们经过每个游览点,都可以品尝到一颗对应种类的糖果。
大家对不同类型糖果的喜爱程度都不尽相同。根据游客们的反馈打分,我们得到了糖果的美味指数,第 i 种糖果的美味指数为 V i 。另外,如果一位游客反复地品尝同一种类的糖果,他肯定会觉得有一些腻。根据量化统计,我们得到了游客第 i 次品尝某类糖果的新奇指数 W i 。如果一位游客第 i 次品尝第 j 种糖果,那么他的愉悦指数 H 将会增加对应的美味指数与新奇指数的乘积,即 V j W i 。这位游客游览公园的愉悦指数最终将是这些乘积的和。
当然,公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时,一些糖果点所发放的糖果种类可能会更改(也只会是 m 种中的一种),这样的目的是能够让游客们总是感受到惊喜。
糖果公园的工作人员小 A 接到了一个任务,那就是 根据公园最近的数据统计出每位游客游玩公园的愉悦指数 。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕,作为小 A 最好的朋友,你决定帮他一把。
【输入文件】
从文件 park.in 中读入数据。
第一行包含三个正整数 n, m, q,分别表示游览点个数、糖果种类数和操作次数。
第二行包含 m 个正整数 V 1 , V 2 , ..., V m 。
第三行包含 n 个正整数 W 1 , W 2 , ..., W n 。

第四行到第 n + 2 行,每行包含两个正整数 A i , B i ,表示这两个游览点之间有路径可以直接到达。
第 n + 3 行包含 n 个正整数 C 1 , C 2 , ..., C n 。
接下来 q 行,每行包含三个整数 Type, x, y,表示一次操作:
若 Type 为 0,则 1 ≤ x ≤ n,1 ≤ y ≤ m,表示将编号为 x 的游览点发放的糖果类型改为 y;
若 Type 为 1,则 1 ≤ x, y ≤ n,表示对出发点为 x,终止点为 y 的路线询问愉悦指数。
【输出文件】
输出到文件 park.out 中。
按照输入的先后顺序,对于每个 Type 为 1 的操作输出一行,用一个正整数
表示答案。

样例一

input

4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2

output

84
131
27
84

正解：树上带修改莫队

解题报告：

　　这道题算是树上带修改莫队的经典题了。

　　我卡常数卡了好久都没过，结果发现是我树上分块写萎了......

　　首先这道题求的是$\sum^{m}_{i=1}$ ( $val[i]*$ $\sum^{Tim[i]}_{j=1}w[j]$)

　　$Tim[i]$表示颜色i的出现次数，$val[i]$表示颜色i的价值，$w[j]$表示第j次的新奇指数

　　对于一种颜色，显然我们只关心一条路径上有多少个即可，顺序并不影响。

　　所以我们考虑带修改莫队的模式，按$(l/block,r/block,t)$排序，当然这道题并不是直接除以$block$，而是先在树上分块（分块的方式同BZOJ1086王室联邦），再按每个点所在的块的编号来排序。

　　接着，我们就可以操作了。

　　修改操作显然就是先消除原来颜色的影响，再加入新的颜色的影响，并且与序列带修改莫队相同的是，也是模拟时间流逝和倒流。

　　关键在于我们如何从这一次询问转移到下一次询问。考虑我们树上的所有结点，实际上可以认为是$01$状态——计入答案或者未计入答案。

　　那么我就可以用类似于异或的思想来执行操作（不妨设为$change$操作），比如：计入答案再从答案中去掉，等于异或了两次$1$，就等于原来的数。假设这次的起点、终点为$u$、$v$，上次为$x$、$y$，那么我可以对$x$到$u$的路径、$v$到$y$的路径执行$change$操作，直接查询即可。

　　在纸上作图就可以发现上述做法的妙处，可以大大避免大量两次$change$操作变回自身的情况。$change$操作直接暴力做即可.

　　而为了方便，需要给每个结点一个标记，表示是否已经被计入答案中了（因为是否计入答案中显然会产生不一样的影响）。

　　附：复杂度证明：

　　　　设block_num为块数，block_size为块的大小，则有block_num×block_size=n，在证明中我们假设n，q同阶。

　　　　设块对(block_i,block_j)，易知这样的块对不会超过block_size²个。

　　　　对于块对内的操作：我们考虑总复杂度，左端点共移动至多O(q×block_size)，右端点亦是。时间共移动至多O(block_num²×q)。故这一部分的复杂度为O(n×(block_size+block_num²))。

　　　　对于块与块之间的操作，不超过block_num²次：左端第移动一次，最多O(n)，右端点亦是如此。时间最多移动O(q)=O(n)。故这一部分复杂度为O(block_num²×n)。

　　　　故总复杂度为O(n×(block_size+block_num²))。

　　　　可以证明当block_size=n^2/3时，block_num=n^1/3，复杂度最优，为O(n^5/3)。

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100011;
const int MAXM = 200011;
int n,m,q,val[MAXN],w[MAXN],col[MAXN],pre[MAXN],belong[MAXN],stack[MAXN],top,Tim[MAXN],cc,vis[MAXN];
int ecnt,first[MAXN],to[MAXM],next[MAXM],cnt1,cnt2,block,deep[MAXN],f[MAXN][18],dfn[MAXN];
LL A[MAXN],ans;
struct ask{int l,r,t,lb,rb,id;}a[MAXN];
struct UP{int x,y,pre;}b[MAXN];
inline bool cmp(ask q,ask qq){
	if(q.lb==qq.lb && q.rb==qq.rb) return q.t<qq.t;
	if(q.lb==qq.lb) return q.rb<qq.rb;
	return q.lb<qq.lb;
}
inline void link(int x,int y){ next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; }
inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}

inline int lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y); int t=0; while((1<<t)<=deep[x]) t++; t--;
	for(int i=t;i>=0;i--) if(deep[x]-(1<<i)>=deep[y]) x=f[x][i]; if(x==y) return y;
	for(int i=t;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0];
}

inline int dfs(int x,int fa){
	int remain=0; dfn[x]=++cc;
	for(int i=first[x];i;i=next[i]) {
		int v=to[i]; if(v==fa) continue;
		f[v][0]=x; deep[v]=deep[x]+1; remain+=dfs(v,x);
		if(remain>=block) {
			ecnt++;
			while(remain>0)/*!!!*/ belong[stack[top]]=ecnt,top--,remain--;
			remain=0;
		}
	}
	stack[++top]=x;
	return remain+1;
}

inline void update(int x){//改变x点的状态
	if(vis[x]) {//从答案中消除
		vis[x]=0;//标记为未计入答案
		ans-=(LL)w[ Tim[col[x]] ]*val[col[x]];
		Tim[col[x]]--;
	}
	else{//从答案中加入
		vis[x]=1;
		Tim[col[x]]++;
		ans+=(LL)w[ Tim[col[x]] ]*val[col[x]];//!!!
	}
}

inline void change(int x,int y){
	while(x!=y) {
		if(deep[x]<deep[y]) update(y),y=f[y][0];
		else update(x),x=f[x][0];
	}
}

inline void modify(int x,int C){//把x修改为颜色C
	if(!vis[x]) col[x]=C;
	else {
		update(x);
		col[x]=C;
		update(x);
	}
}

inline void work(){
	n=getint(); m=getint(); q=getint(); int x,y; block=(int)pow(n,0.60);
	for(int i=1;i<=m;i++) val[i]=getint();
	for(int i=1;i<=n;i++) w[i]=getint();
	for(int i=1;i<n;i++) { x=getint(); y=getint(); link(x,y); link(y,x); }
	for(int i=1;i<=n;i++) col[i]=getint(),pre[i]=col[i];
	ecnt=0; deep[1]=1; dfs(1,0);
	int ljh,LCA; for(int j=1;j<=17;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
	for(int o=1;o<=q;o++) {
		ljh=getint(); x=getint(); y=getint();
		if(ljh==0) { b[++cnt2].pre=pre[x]; b[cnt2].x=x; b[cnt2].y=y; pre[x]=y;/*!!!*/ }
		else{
			if(dfn[x]>dfn[y]) swap(x,y);
			a[++cnt1].l=x; a[cnt1].r=y;
			a[cnt1].lb=belong[x]; a[cnt1].rb=belong[y];
			a[cnt1].t=cnt2; a[cnt1].id=cnt1;
		}
	}
	sort(a+1,a+cnt1+1,cmp); cnt2=a[1].t;
	for(int i=1;i<=a[1].t;i++) modify(b[i].x,b[i].y);
	change(a[1].l,a[1].r); LCA=lca(a[1].l,a[1].r);
	update(LCA);//lca并未处理
	A[a[1].id]=ans;
	update(LCA);
	for(int i=2;i<=cnt1;i++) {
		while(cnt2<a[i].t) cnt2++,modify(b[cnt2].x,b[cnt2].y);
		while(cnt2>a[i].t) modify(b[cnt2].x,b[cnt2].pre),cnt2--;
		change(a[i-1].l,a[i].l);
		change(a[i-1].r,a[i].r);
		LCA=lca(a[i].l,a[i].r);
		update(LCA);
		A[a[i].id]=ans;
		update(LCA);
	}
	for(int i=1;i<=cnt1;i++) printf("%lld\n",A[i]);
}

int main()
{
    work();
    return 0;
}