树分块
老早（大约一个月以前？）就听说这道神题了……orz rausen
一直拖到现在才做……发现还是不会呢= = 只好也去Orz了Hzwer和zky
http://hzwer.com/5250.html http://blog.csdn.net/iamzky/article/details/42125999这个树上莫队真的蛮神奇的……
1.对于每个查询，记录它是在第几次修改之后的;
2.以左端点所在块为第一关键字、右端点所在块为第二关键字、时间（第几次修改之后的查询）为第三关键字进行排序;
3.对于每个查询，先进行时间上的移动（这个只需对变化了的点进行单点修改即可，有点小Z的袜子中 +1-1的感觉）再进行查询序列的移动（用之前讲的vfk的方法……）至于第二步就跟普通的树分块一样了么……
注意：由于时间移动既有向前也有向后的，所以除了要记录是把哪个点变成了什么糖果，还要记录变化前的原来的状态（时光回溯时用）（用“时光回溯”这个名字是不是十分高大上～～）
错误：1.所有数据点的答案范围都是long long！！
2.读入单点修改糖果种类的时候，pre[x]=y; 写成了 pre[c2]=y; QAQ唉细节啊细节！！！pre数组是对点进行“时光回溯”保存的，不是对修改序号进行保存！！！理解不到位啊……（白问大视野要数据了……）
1 /************************************************************** 2 Problem: 3052 3 User: Tunix 4 Language: C++ 5 Result: Accepted 6 Time:117744 ms 7 Memory:25256 kb 8 ****************************************************************/ 9 10 //BZOJ 3052 11 #include<cmath> 12 #include<cstdio> 13 #include<cstdlib> 14 #include<cstring> 15 #include<iostream> 16 #include<algorithm> 17 #define rep(i,n) for(int i=0;i<n;++i) 18 #define F(i,j,n) for(int i=j;i<=n;++i) 19 #define D(i,j,n) for(int i=j;i>=n;--i) 20 using namespace std; 21 22 int getint(){ 23 int v=0,sign=1; char ch=getchar(); 24 while(!isdigit(ch)) {if(ch=='-') sign=-1; ch=getchar();} 25 while(isdigit(ch)) {v=v*10+ch-'0'; ch=getchar();} 26 return v*=sign; 27 } 28 typedef long long LL; 29 /******************tamplate*********************/ 30 const int N=100086; 31 LL w[N],v[N]; 32 int n,m,Q; 33 int head[N],next[N<<1],to[N<<1],cnt; 34 void add(int x,int y){ 35 to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; 36 to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt; 37 } 38 /*******************edge************************/ 39 int B; 40 int st[N],top,deep[N],belong[N],tot; 41 int fa[N][25],bin[25]; 42 void dfs(int x){ 43 int bottom=top; 44 F(i,1,20) 45 if(deep[x]>=bin[i]) 46 fa[x][i]=fa[fa[x][i-1]][i-1]; 47 else break; 48 for(int i=head[x];i;i=next[i]) 49 if (to[i]!=fa[x][0]){ 50 fa[to[i]][0]=x; 51 deep[to[i]]=deep[x]+1; 52 dfs(to[i]); 53 if(top-bottom>=B){ 54 ++tot; 55 while(top!=bottom) 56 belong[st[top--]]=tot; 57 } 58 } 59 st[++top]=x; 60 } 61 int LCA(int x,int y){ 62 if(deep[x]<deep[y]) swap(x,y); 63 int t=deep[x]-deep[y]; 64 for(int i=0;bin[i]<=t;i++) 65 if(t&bin[i]) x=fa[x][i]; 66 D(i,20,0) 67 if(fa[x][i]!=fa[y][i]) 68 x=fa[x][i],y=fa[y][i]; 69 if(x==y) return x; 70 return fa[x][0]; 71 } 72 /*********************dfs&&LCA******************/ 73 struct ques{ 74 int x,y,ti,num; 75 bool operator < (const ques&now)const{ 76 if(belong[x]==belong[now.x]){ 77 if(belong[y]==belong[now.y]) return ti<now.ti; 78 else return belong[y]<belong[now.y]; 79 } 80 else return belong[x]<belong[now.x]; 81 } 82 }q[N]; 83 struct Time{ 84 int x,y,pre; 85 }change[N]; 86 int pre[N]; 87 88 LL ans=0,answer[N]; 89 int c[N],num[N],now; 90 bool used[N]; 91 /*****************分块变量声明******************/ 92 void work(int x){ 93 if (used[x]){ 94 ans-=v[c[x]]*w[num[c[x]]]; num[c[x]]--; used[x]=0; 95 } 96 else{ 97 num[c[x]]++; ans+=v[c[x]]*w[num[c[x]]]; used[x]=1; 98 } 99 } 100 void Xor(int x,int y){ 101 while(x!=y) 102 if(deep[x]>deep[y]) {work(x);x=fa[x][0];} 103 else {work(y); y=fa[y][0];} 104 } 105 void Change(int x,int y){//将点x的糖果改为第y种 (权值改为y) 106 if(used[x]){work(x); c[x]=y; work(x);} 107 else c[x]=y; 108 } 109 void TimeMachine(int tarti){ 110 for(int i=now+1;i<=tarti;i++) Change(change[i].x,change[i].y); 111 for(int i=now;i>tarti;i--) Change(change[i].x,change[i].pre); 112 now=tarti; 113 } 114 /*****************分块函数声明******************/ 115 int main(){ 116 bin[0]=1; F(i,1,20) bin[i]=bin[i-1]<<1; 117 118 n=getint(); m=getint(); Q=getint(); 119 B=pow(n,2.0/3.0); 120 int x,y; 121 F(i,1,m) v[i]=getint();//美味指数 122 F(i,1,n) w[i]=getint();//新奇指数 123 F(i,2,n){ 124 x=getint(); y=getint(); 125 add(x,y); 126 } 127 128 dfs(1); 129 tot++; 130 while(top) belong[st[top--]]=tot; 131 F(i,1,n) pre[i]=c[i]=getint();//每个节点的糖果种类 132 133 int cmd,c1=0,c2=0; 134 F(i,1,Q){ 135 cmd=getint(); x=getint(); y=getint(); 136 if (cmd){ 137 c2++; 138 if(belong[x]>belong[y]) swap(x,y); 139 q[c2]=(ques){x,y,c1,c2};//记录是第几次修改之后的查询 140 } 141 else{ 142 c1++; 143 change[c1]=(Time){x,y,pre[x]}; 144 pre[x]=y; 145 //有点前向星的感觉,pre[i]保存第i个节点当前是什么种类的糖果 146 } 147 } 148 sort(q+1,q+c2+1); 149 //读入&&初始化 end 150 151 int lca=LCA(q[1].x,q[1].y); 152 TimeMachine(q[1].ti); 153 Xor(q[1].x,q[1].y); 154 work(lca); 155 answer[q[1].num]=ans; 156 work(lca); 157 F(i,2,c2){ 158 TimeMachine(q[i].ti); 159 Xor(q[i-1].x,q[i].x); 160 Xor(q[i-1].y,q[i].y); 161 lca=LCA(q[i].x,q[i].y); 162 work(lca); 163 answer[q[i].num]=ans; 164 work(lca); 165 } 166 F(i,1,c2) printf("%lld ",answer[i]); 167 return 0; 168 }