Title
P4074 [WC2013]糖果公园
Solution
注意莫队中左右指针的判断条件别打错，qr->ql
在树上莫队的基础上加一维时间轴，然后把指针移来移去，
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std
;
const int N
=2e5+5;
struct node
{
int l
,r
,lca
,t
,id
;
}q
[N
];
struct node1
{
int y
,next
;
}a
[N
];
struct node2
{
int l
,r
;
}g
[N
];
int head
[N
],n
,m
,Q
,V
[N
],W
[N
],C
[N
],cnt
[N
],size
,bg
[N
],tot
;
int dep
[N
],f
[N
][30],T
=20,first
[N
],last
[N
],d
[N
],num
;
int cntq
,cntc
;
ll ans
[N
],val
;
int vis
[N
];
int read(){
int p
=0; char c
=getchar();
while(!isdigit(c
)) c
=getchar();
while(isdigit(c
)) p
=(p
<<3)+(p
<<1)+c
-48,c
=getchar();
return p
;
}
void add(int x
,int y
){
a
[++tot
]=(node1
){y
,head
[x
]}; head
[x
]=tot
;
}
bool cmp(node x
,node y
){
return (bg
[x
.l
]^bg
[y
.l
])?bg
[x
.l
]<bg
[y
.l
]:((bg
[x
.r
]^bg
[y
.r
])?bg
[x
.r
]<bg
[y
.r
]:x
.t
<y
.t
);
}
void dfs(int x
){
d
[++num
]=x
; first
[x
]=num
;
for(int i
=head
[x
];i
;i
=a
[i
].next
){
int y
=a
[i
].y
;
if (y
!=f
[x
][0]){
dep
[y
]=dep
[x
]+1;
f
[y
][0]=x
;
rep(i
,1,T
) f
[y
][i
]=f
[f
[y
][i
-1]][i
-1];
dfs(y
);
}
}
d
[++num
]=x
; last
[x
]=num
;
}
int getlca(int x
,int y
){
if (dep
[x
]<dep
[y
]) swap(x
,y
);
for(int i
=T
;i
>=0;i
--) if (dep
[f
[x
][i
]]>=dep
[y
]) x
=f
[x
][i
];
if (x
==y
) return x
;
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];
}
void work(int x
){
int y
=C
[x
];
vis
[x
]?(val
-=1ll*W
[cnt
[y
]--]*V
[y
]):(val
+=1ll*W
[++cnt
[y
]]*V
[y
]);
vis
[x
]^=1;
}
void sol(int x
){
if (vis
[g
[x
].l
]){
work(g
[x
].l
);
swap(C
[g
[x
].l
],g
[x
].r
);
work(g
[x
].l
);
} else swap(C
[g
[x
].l
],g
[x
].r
);
}
int main(){
n
=read(),m
=read(),Q
=read();
rep(i
,1,m
) V
[i
]=read();
rep(i
,1,n
) W
[i
]=read();
rep(i
,1,n
-1){
int x
=read(),y
=read();
add(x
,y
);
add(y
,x
);
}
rep(i
,1,n
) C
[i
]=read();
dep
[1]=1;
dfs(1);
size
=pow(num
,2.0/3.0);
rep(i
,1,num
) bg
[i
]=(i
-1)/size
+1;
rep(i
,1,Q
){
int Type
=read(),x
=read(),y
=read();
if (Type
==0){
g
[++cntc
].l
=x
;
g
[cntc
].r
=y
;
} else {
int l
=x
,r
=y
;
int lca
=getlca(l
,r
);
if (first
[l
]>first
[r
]) swap(l
,r
);
if (lca
==l
){
q
[++cntq
].l
=first
[l
];
q
[cntq
].r
=first
[r
];
} else {
q
[++cntq
].l
=last
[l
];
q
[cntq
].r
=first
[r
];
q
[cntq
].lca
=lca
;
}
q
[cntq
].t
=cntc
;
q
[cntq
].id
=cntq
;
}
}
sort(q
+1,q
+cntq
+1,cmp
);
int l
=1,r
=0,t
=0;
rep(i
,1,cntq
){
int ql
=q
[i
].l
,qr
=q
[i
].r
,lca
=q
[i
].lca
,qt
=q
[i
].t
;
while (l
>ql
) work(d
[--l
]);
while (r
<qr
) work(d
[++r
]);
while (l
<ql
) work(d
[l
++]);
while (r
>qr
) work(d
[r
--]);
while (t
<qt
) sol(++t
);
while (t
>qt
) sol(t
--);
if (lca
) work(lca
);
ans
[q
[i
].id
]=val
;
if (lca
) work(lca
);
}
rep(i
,1,cntq
) printf("%lld\n",ans
[i
]);
return 0;
}
