树分块
老早（大约一个月以前？）就听说这道神题了……orz rausen
一直拖到现在才做……发现还是不会呢= = 只好也去Orz了Hzwer和zky
http://hzwer.com/5250.html http://blog.****.net/iamzky/article/details/42125999这个树上莫队真的蛮神奇的……
1.对于每个查询，记录它是在第几次修改之后的;
2.以左端点所在块为第一关键字、右端点所在块为第二关键字、时间（第几次修改之后的查询）为第三关键字进行排序;
3.对于每个查询，先进行时间上的移动（这个只需对变化了的点进行单点修改即可，有点小Z的袜子中 +1-1的感觉）再进行查询序列的移动（用之前讲的vfk的方法……）至于第二步就跟普通的树分块一样了么……
注意：由于时间移动既有向前也有向后的，所以除了要记录是把哪个点变成了什么糖果，还要记录变化前的原来的状态（时光回溯时用）（用“时光回溯”这个名字是不是十分高大上～～）
错误：1.所有数据点的答案范围都是long long！！
2.读入单点修改糖果种类的时候，pre[x]=y; 写成了 pre[c2]=y; QAQ唉细节啊细节！！！pre数组是对点进行“时光回溯”保存的，不是对修改序号进行保存！！！理解不到位啊……（白问大视野要数据了……）
/**************************************************************
Problem: 3052
User: Tunix
Language: C++
Result: Accepted
Time:117744 ms
Memory:25256 kb
****************************************************************/ //BZOJ 3052
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std; int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*=sign;
}
typedef long long LL;
/******************tamplate*********************/
const int N=;
LL w[N],v[N];
int n,m,Q;
int head[N],next[N<<],to[N<<],cnt;
void add(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt;
}
/*******************edge************************/
int B;
int st[N],top,deep[N],belong[N],tot;
int fa[N][],bin[];
void dfs(int x){
int bottom=top;
F(i,,)
if(deep[x]>=bin[i])
fa[x][i]=fa[fa[x][i-]][i-];
else break;
for(int i=head[x];i;i=next[i])
if (to[i]!=fa[x][]){
fa[to[i]][]=x;
deep[to[i]]=deep[x]+;
dfs(to[i]);
if(top-bottom>=B){
++tot;
while(top!=bottom)
belong[st[top--]]=tot;
}
}
st[++top]=x;
}
int LCA(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for(int i=;bin[i]<=t;i++)
if(t&bin[i]) x=fa[x][i];
D(i,,)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if(x==y) return x;
return fa[x][];
}
/*********************dfs&&LCA******************/
struct ques{
int x,y,ti,num;
bool operator < (const ques&now)const{
if(belong[x]==belong[now.x]){
if(belong[y]==belong[now.y]) return ti<now.ti;
else return belong[y]<belong[now.y];
}
else return belong[x]<belong[now.x];
}
}q[N];
struct Time{
int x,y,pre;
}change[N];
int pre[N]; LL ans=,answer[N];
int c[N],num[N],now;
bool used[N];
/*****************分块变量声明******************/
void work(int x){
if (used[x]){
ans-=v[c[x]]*w[num[c[x]]]; num[c[x]]--; used[x]=;
}
else{
num[c[x]]++; ans+=v[c[x]]*w[num[c[x]]]; used[x]=;
}
}
void Xor(int x,int y){
while(x!=y)
if(deep[x]>deep[y]) {work(x);x=fa[x][];}
else {work(y); y=fa[y][];}
}
void Change(int x,int y){//将点x的糖果改为第y种 (权值改为y)
if(used[x]){work(x); c[x]=y; work(x);}
else c[x]=y;
}
void TimeMachine(int tarti){
for(int i=now+;i<=tarti;i++) Change(change[i].x,change[i].y);
for(int i=now;i>tarti;i--) Change(change[i].x,change[i].pre);
now=tarti;
}
/*****************分块函数声明******************/
int main(){
bin[]=; F(i,,) bin[i]=bin[i-]<<; n=getint(); m=getint(); Q=getint();
B=pow(n,2.0/3.0);
int x,y;
F(i,,m) v[i]=getint();//美味指数
F(i,,n) w[i]=getint();//新奇指数
F(i,,n){
x=getint(); y=getint();
add(x,y);
} dfs();
tot++;
while(top) belong[st[top--]]=tot;
F(i,,n) pre[i]=c[i]=getint();//每个节点的糖果种类 int cmd,c1=,c2=;
F(i,,Q){
cmd=getint(); x=getint(); y=getint();
if (cmd){
c2++;
if(belong[x]>belong[y]) swap(x,y);
q[c2]=(ques){x,y,c1,c2};//记录是第几次修改之后的查询
}
else{
c1++;
change[c1]=(Time){x,y,pre[x]};
pre[x]=y;
//有点前向星的感觉,pre[i]保存第i个节点当前是什么种类的糖果
}
}
sort(q+,q+c2+);
//读入&&初始化 end int lca=LCA(q[].x,q[].y);
TimeMachine(q[].ti);
Xor(q[].x,q[].y);
work(lca);
answer[q[].num]=ans;
work(lca);
F(i,,c2){
TimeMachine(q[i].ti);
Xor(q[i-].x,q[i].x);
Xor(q[i-].y,q[i].y);
lca=LCA(q[i].x,q[i].y);
work(lca);
answer[q[i].num]=ans;
work(lca);
}
F(i,,c2) printf("%lld\n",answer[i]);
return ;
}