QTREE1
把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了...
但是注意查询时 LCA 是不能查的，需要判一下。
而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQ
SPOJ AC代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#define re register
#define swap(x,y) { int tmp=x; x=y; y=tmp; }
int max(int a,int b) { return a>b?a:b; }
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
#define N (10000+10)
int n,val[N];
struct edge { int v,w,nxt; } e[N<<1];
int head[N],x[N],y[N],e_cnt=0;
void addEdge(int u,int v,int w) {
++e_cnt;
e[e_cnt].v=v,e[e_cnt].w=w,e[e_cnt].nxt=head[u],head[u]=e_cnt;
}
int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],rl[N],tim=0;
void dfs1(int u,int f) {
fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w; if (v==f) continue;
val[v]=w,dfs1(v,u),sz[u]+=sz[v];
if (sz[v]>sz[hson[u]]) hson[u]=v;
}
}
void dfs2(int u,int anc) {
dfn[u]=++tim,rl[tim]=u,top[u]=anc;
if (hson[u]) dfs2(hson[u],anc);
for (re int i=head[u];i;i=e[i].nxt)
if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}
#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2];
void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
void build(int o,int l,int r) {
if (l==r) { maxv[o]=val[rl[l]]; return; }
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(o);
}
void modify(int o,int l,int r,int p,int w) {
if (l==r) { maxv[o]=w; return; }
int mid=(l+r)>>1;
if (p<=mid) modify(ls,l,mid,p,w);
else modify(rs,mid+1,r,p,w);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return maxv[o];
int mid=(l+r)>>1,res=0;
if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
return res;
}
#undef ls
#undef rs
int Query(int u,int v) {
int tu=top[u],tv=top[v],res=0;
while (tu!=tv) {
if (dep[tu]<dep[tv]) { swap(tu,tv); swap(u,v); }
res=max(res,query(1,1,n,dfn[tu],dfn[u]));
u=fa[tu],tu=top[u];
}
if (dep[u]<dep[v]) swap(u,v);
res=max(res,query(1,1,n,dfn[v]+1,dfn[u]));
return res;
}
void init() {
n=e_cnt=tim=0;
memset(head,0,sizeof(head));
memset(hson,0,sizeof(hson));
memset(top,0,sizeof(top));
memset(maxv,0,sizeof(maxv));
}
int main() {
int T=read();
while (T--) {
init();
n=read();
for (re int i=1;i<n;++i) {
int u=read(),v=read(),w=read();
x[i]=u,y[i]=v;
addEdge(u,v,w),addEdge(v,u,w);
}
dfs1(1,0),dfs2(1,1); build(1,1,n);
while (233) {
char op[10]; scanf("%s",op);
if (op[0]=='D') break;
if (op[0]=='C') {
int i=read(),w=read(),u=dep[x[i]]>dep[y[i]]?x[i]:y[i];
modify(1,1,n,dfn[u],w);
} else {
int u=read(),v=read();
if (u==v) puts("0");
else printf("%d\n",Query(u,v));
}
}
}
return 0;
}QTREE2
DIST 操作只需要维护树上前缀和即可求出答案。
KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即可求出。
所以只需要写一个倍增 LCA 和一个倍增找 $k$ 次祖先就好了。
SPOJ AC代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=10000+10;
int n;
struct edge { int v,w,nxt; } e[N<<1];
int head[N],e_cnt=0;
inline void addEdge(int u,int v,int w) {
e[++e_cnt]=(edge){v,w,head[u]},head[u]=e_cnt;
}
int dep[N],dis[N],f[14][N];
inline void dfs(int u,int fa) {
for (re int i=1;i<=13;++i) f[i][u]=f[i-1][f[i-1][u]];
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w; if (v==fa) continue;
dep[v]=dep[u]+1,dis[v]=dis[u]+w,f[0][v]=u;
dfs(v,u);
}
}
inline int getLCA(int u,int v) {
if (dep[u]<dep[v]) swap(u,v);
for (re int i=13;~i;--i)
if (dep[f[i][u]]>dep[v]) u=f[i][u];
if (dep[u]!=dep[v]) u=f[0][u];
for (re int i=13;~i;--i)
if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
if (u!=v) u=f[0][u];
return u;
}
inline int find(int u,int k) {
for (re int i=13;~i;--i)
if (k&(1<<i)) u=f[i][u];
return u;
}
inline void init() {
memset(head,0,sizeof(head)),e_cnt=0;
}
int main() {
int T=read();
while (T--) {
init();
n=read();
for (re int i=1;i<n;++i) {
int u=read(),v=read(),w=read();
addEdge(u,v,w),addEdge(v,u,w);
}
dfs(1,0);
while (233) {
char op[10]; scanf("%s",op);
if (op[1]=='O') break;
if (op[0]=='D') {
int u=read(),v=read(),t=getLCA(u,v);
printf("%d\n",dis[u]+dis[v]-(dis[t]<<1));
} else {
int u=read(),v=read(),t=getLCA(u,v),k=read();
int L=dep[u]-dep[t]+1,R=dep[v]-dep[t]+1;
if (L>=k) printf("%d\n",find(u,k-1));
else printf("%d\n",find(v,R-(k-L+1)));
}
}
}
return 0;
}QTREE3
树链剖分，每条重链开一个 set 维护所有黑点。
修改直接 insert / erase ，查询就跳重链跳到根并更新答案即可。
SPOJ AC代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,Q,c[N];
struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
static int cnt=0;
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],id[N],tim=0;
void dfs1(int u,int f) {
fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; if (v==f) continue;
dfs1(v,u),sz[u]+=sz[v];
if (sz[v]>sz[hson[u]]) hson[u]=v;
}
}
void dfs2(int u,int anc) {
dfn[u]=++tim,id[tim]=u,top[u]=anc;
if (hson[u]) dfs2(hson[u],anc);
for (re int i=head[u];i;i=e[i].nxt)
if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}
set<int> S[N];
int main() {
n=read(),Q=read();
for (re int i=1;i<n;++i) {
int u=read(),v=read();
addEdge(u,v),addEdge(v,u);
}
dfs1(1,0),dfs2(1,1);
while (Q--) {
int op=read(),u=read();
if (!op) {
c[u]^=1;
if (c[u]) S[top[u]].insert(dfn[u]);
else S[top[u]].erase(dfn[u]);
} else {
int res=-1;
while (u) {
if (S[top[u]].size()) {
int v=id[*S[top[u]].begin()];
if (dep[v]<=dep[u]) res=v;
}
u=fa[top[u]];
}
printf("%d\n",res);
}
}
return 0;
}QTREE4
其实和捉迷藏那题是一样的...
首先建出点分树，然后每个点开两个堆，一个维护点分子树中所有白点到 $u$ 在点分树上父亲的距离，一个维护所有儿子的前一个堆的堆顶。
然后再开一个堆记一下所有点的最长链与次长链之和。那么就很好算答案了。
然后修改的话就在点分树上暴跳父亲并修改一些东西。
SPOJ AC代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n;
struct edge { int v,w,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int w) {
static int cnt=0;
e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}
struct Heap {
priority_queue<int> Q,O;
inline void push(int x) { Q.push(x); }
inline void del(int x) { O.push(x); }
inline void remove() {
while (!O.empty()&&Q.top()==O.top()) Q.pop(),O.pop();
}
inline int size() { return Q.size()-O.size(); }
inline void pop() { remove(); Q.pop(); }
inline int top() { remove(); return Q.empty()?0:Q.top(); }
inline int top2() {
if (size()<2) return 0;
int tmp=top(); pop(); int res=top();
push(tmp); return res;
}
} ans,A[N],B[N];
inline void push(Heap& x) { if (x.size()>1) ans.push(x.top()+x.top2()); }
inline void del(Heap& x) { if (x.size()>1) ans.del(x.top()+x.top2()); }
namespace OT {
int lg[N<<2],pos[N<<1],st[19][N<<2],dep[N],dis[N],tot=0;
inline void dfs(int u,int fa) {
st[0][++tot]=u,pos[u]=tot;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w; if (v==fa) continue;
dep[v]=dep[u]+1,dis[v]=dis[u]+w;
dfs(v,u),st[0][++tot]=u;
}
}
inline int cmp(int a,int b) { return dep[a]<dep[b]?a:b; }
inline void init_rmq() {
for (re int i=2;i<=tot;++i) lg[i]=lg[i>>1]+1;
for (re int i=1;i<=18;++i)
for (re int j=1;j+(1<<i)-1<=tot;++j)
st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
inline int getdis(int u,int v) {
if (pos[u]>pos[v]) swap(u,v);
int t=lg[pos[v]-pos[u]+1];
int lca=cmp(st[t][pos[u]],st[t][pos[v]-(1<<t)+1]);
return dis[u]+dis[v]-(dis[lca]<<1);
}
inline void init() { dfs(1,0); init_rmq(); }
}
namespace T {
int sz[N],vis[N],fa[N];
int sumsz,minsz,root;
inline void getroot(int u,int pa) {
sz[u]=1; int now=0;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; if (v==pa||vis[v]) continue;
getroot(v,u),sz[u]+=sz[v];
now=max(now,sz[v]);
}
now=max(now,sumsz-sz[u]);
if (now<minsz) root=u,minsz=now;
}
inline void dfs(int u,int pa,int anc) {
A[anc].push(OT::getdis(u,fa[anc]));
for (re int i=head[u];i;i=e[i].nxt)
if (e[i].v!=pa&&!vis[e[i].v]) dfs(e[i].v,u,anc);
}
inline void solve(int u,int pa) {
vis[u]=1,fa[u]=pa;
dfs(u,0,u),B[u].push(0),B[pa].push(A[u].top());
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; if (v==pa||vis[v]) continue;
minsz=n,sumsz=sz[v]; getroot(v,u);
solve(root,u);
}
push(B[u]);
}
inline void build() {
root=0,minsz=sumsz=n;
getroot(1,0); solve(root,0);
}
int col[N];
inline void whiten(int u) {
del(B[u]),B[u].push(0),push(B[u]);
for (re int i=u;fa[i];i=fa[i]) {
del(B[fa[i]]);
if (A[i].size()) B[fa[i]].del(A[i].top());
A[i].push(OT::getdis(u,fa[i]));
B[fa[i]].push(A[i].top());
push(B[fa[i]]);
}
}
inline void blacken(int u) {
del(B[u]),B[u].del(0),push(B[u]);
for (re int i=u;fa[i];i=fa[i]) {
del(B[fa[i]]);
if (A[i].size()) B[fa[i]].del(A[i].top());
A[i].del(OT::getdis(u,fa[i]));
if (A[i].size()) B[fa[i]].push(A[i].top());
push(B[fa[i]]);
}
}
inline void query() {
int Q=read(),num=n;
while (Q--) {
char op[2]; scanf("%s",op);
if (op[0]=='A') {
if (!num) puts("They have disappeared.");
else if (num==1) puts("0");
else printf("%d\n",max(0,ans.top()));
} else {
int u=read();
if (col[u]) whiten(u),col[u]=0,++num;
else blacken(u),col[u]=1,--num;
}
}
}
}
int main() {
n=read();
for (re int i=1;i<n;++i) {
int u=read(),v=read(),w=read();
addEdge(u,v,w),addEdge(v,u,w);
}
OT::init(); T::build(); T::query();
return 0;
}QTREE5
显然可以动态点分治，但是这东西我再也不想写了...
考虑一个 LCT 做法。
每个节点维护一个 $lm$ 和 $rm$ ，分别表示该节点所在的 Splay 中最浅的/最深的节点能到的子树中最近的白点的距离。
考虑这个东西怎么维护。因为 $lm$ 和 $rm$ 类似，这里只考虑 $lm$ 。
显然 $lm_u$ 是以下两部分的最小值：
- 左子树的答案。
- 左子树的 $size$ + 右子树的答案 +1。
如果 $u$ 是白点的话，还要加上一部分：左子树的 $size$ 。
考虑怎么算右子树的答案。对每个节点维护一个 multiset ，维护所有虚子树的答案即可。
这个东西在 access 的时候顺便维护一下就好了。
查询就直接 makeroot ，然后查 $lm$ 就好了。
注意 makeroot 时需要 reverse ，而 reverse 时要把 $lm$ 和 $rm$ 也交换！
SPOJ AC代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,Q,col[N];
struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
static int cnt=0;
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
struct Link_Cut_Tree {
int fa[N],ch[N][2],sz[N],rev[N];
int lm[N],rm[N];
multiset<int> S[N];
int sta[N];
inline int fir(int x) { return S[x].empty()?1e9:*(S[x].begin()); }
inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
inline void reverse(int x) {
swap(ch[x][0],ch[x][1]),swap(lm[x],rm[x]),rev[x]^=1;
}
inline void pushup(int x) {
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
lm[x]=min(lm[ch[x][0]],sz[ch[x][0]]+min(fir(x),lm[ch[x][1]]+1));
if (col[x]) lm[x]=min(lm[x],sz[ch[x][0]]);
rm[x]=min(rm[ch[x][1]],sz[ch[x][1]]+min(fir(x),rm[ch[x][0]]+1));
if (col[x]) rm[x]=min(rm[x],sz[ch[x][1]]);
}
inline void pushdown(int x) {
if (rev[x]) {
if (ch[x][0]) reverse(ch[x][0]);
if (ch[x][1]) reverse(ch[x][1]);
rev[x]=0;
}
}
inline void rotate(int x) {
int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
if (nroot(y)) ch[z][ch[z][1]==y]=x;
ch[x][!k]=y,ch[y][k]=w;
if (w) fa[w]=y; fa[y]=x,fa[x]=z;
pushup(y);
}
inline void splay(int x) {
int y=x,z=0; sta[++z]=y;
while (nroot(y)) sta[++z]=y=fa[y];
while (z) pushdown(sta[z--]);
while (nroot(x)) {
y=fa[x],z=fa[y];
if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
rotate(x);
}
pushup(x);
}
inline void access(int x) {
for (re int y=0;x;x=fa[y=x]) {
splay(x);
S[x].insert(lm[ch[x][1]]+1);
ch[x][1]=y;
auto it=S[x].lower_bound(lm[ch[x][1]]+1);
if (it!=S[x].end()&&*it==lm[ch[x][1]]+1) S[x].erase(it);
pushup(x);
}
}
inline void makeroot(int x) { access(x),splay(x),reverse(x); }
} T;
inline void dfs(int u,int f) {
T.fa[u]=f;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; if (v==f) continue;
T.S[u].insert(1e9),T.pushup(u);
dfs(v,u);
}
}
int main() {
T.lm[0]=T.rm[0]=1e9;
n=read();
for (re int i=1;i<n;++i) {
int u=read(),v=read();
addEdge(u,v),addEdge(v,u);
}
dfs(1,0);
Q=read();
while (Q--) {
int op=read(),u=read();
if (!op) {
T.makeroot(u);
col[u]^=1,T.pushup(u);
} else {
T.makeroot(u);
printf("%d\n",T.lm[u]>n?-1:T.lm[u]);
}
}
return 0;
}QTREE6
维护两个 LCT ，一棵维护白点，一棵维护黑点。每次修改暴力 cut 再 link 即可。
然而这样子会被菊花图卡爆。
考虑一种我不会的套路：把 $u$ 的颜色作为 $(u,fa_u)$ 边的颜色。
同样维护两个 LCT ，一棵维护白边，一棵维护黑边。
可以发现每次修改只需要在一棵树中 cut 掉父边，再在另一棵树中 link 父边即可。
查询就直接 findroot ，然后输出重儿子的大小即可。子树大小按照维护子树信息那一套维护。
一个要注意的地方：这棵树被我们强制成了有根树，所以不能 makeroot 。
另一个要注意的地方：根节点要建一个虚点当它的父节点，这样子根节点才会有父边。
SPOJ AC代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,Q,c[N];
struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
static int cnt=0;
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
struct Link_Cut_Tree {
int fa[N],ch[N][2],s[N],si[N];
inline void init() { for (re int i=1;i<=n+1;++i) s[i]=1; }
inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
inline void pushup(int x) { s[x]=s[ch[x][0]]+s[ch[x][1]]+si[x]+1; }
inline void rotate(int x) {
int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
if (nroot(y)) ch[z][ch[z][1]==y]=x;
ch[x][!k]=y,ch[y][k]=w;
if (w) fa[w]=y; fa[y]=x,fa[x]=z;
pushup(y);
}
inline void splay(int x) {
while (nroot(x)) {
int y=fa[x],z=fa[y];
if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
rotate(x);
}
pushup(x);
}
inline void access(int x) {
for (re int y=0;x;x=fa[y=x])
splay(x),si[x]+=s[ch[x][1]],si[x]-=s[ch[x][1]=y];
}
inline int findroot(int x) {
access(x),splay(x);
while (ch[x][0]) x=ch[x][0];
splay(x); return x;
}
inline void link(int x,int y) {
splay(x),access(y),splay(y);
fa[x]=y,si[y]+=s[x],s[y]+=s[x];
}
inline void cut(int x,int y) {
access(x),splay(x);
ch[x][0]=fa[ch[x][0]]=0;
pushup(x);
}
} T[2];
int fa[N];
inline void dfs(int u,int f) {
fa[u]=f,T[0].link(u,f);
for (re int i=head[u];i;i=e[i].nxt)
if (e[i].v!=f) dfs(e[i].v,u);
}
int main() {
n=read(); T[0].init(),T[1].init();
for (re int i=1;i<n;++i) {
int u=read(),v=read();
addEdge(u,v),addEdge(v,u);
}
dfs(1,n+1);
Q=read();
while (Q--) {
int op=read(),u=read();
if (op) T[c[u]].cut(u,fa[u]),c[u]^=1,T[c[u]].link(u,fa[u]);
else {
int rt=T[c[u]].findroot(u);
printf("%d\n",T[c[u]].s[T[c[u]].ch[rt][1]]);
}
}
return 0;
}QTREE7
和 QTREE6 差不多，每个节点开一个 multiset 维护虚儿子的最大值即可。
然后 link 的时候连虚边有点麻烦，可以直接连实边。
SPOJ AC代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,Q;
int c[N],w[N];
struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
static int cnt=0;
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
struct Link_Cut_Tree {
int fa[N],ch[N][2],mx[N]; multiset<int> S[N];
inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
inline void pushup(int x) {
mx[x]=max(w[x],max(mx[ch[x][0]],mx[ch[x][1]]));
if (S[x].size()) mx[x]=max(mx[x],*S[x].rbegin());
}
inline void rotate(int x) {
int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
if (nroot(y)) ch[z][ch[z][1]==y]=x;
ch[x][!k]=y,ch[y][k]=w;
if (w) fa[w]=y; fa[y]=x,fa[x]=z;
pushup(y);
}
inline void splay(int x) {
while (nroot(x)) {
int y=fa[x],z=fa[y];
if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
rotate(x);
}
pushup(x);
}
inline void access(int x) {
for (re int y=0;x;x=fa[y=x]) {
splay(x);
if (ch[x][1]) S[x].insert(mx[ch[x][1]]);
ch[x][1]=y;
if (ch[x][1]) S[x].erase(mx[ch[x][1]]);
pushup(x);
}
}
inline int findroot(int x) {
access(x),splay(x);
while (ch[x][0]) x=ch[x][0];
splay(x); return x;
}
inline void link(int x,int y) {
splay(x),access(y),splay(y);
fa[x]=y,ch[y][1]=x,pushup(y);
}
inline void cut(int x,int y) {
access(x),splay(x);
ch[x][0]=fa[ch[x][0]]=0;
pushup(x);
}
} T[2];
int fa[N];
inline void dfs(int u,int f) {
fa[u]=f,T[c[u]].link(u,f);
for (re int i=head[u];i;i=e[i].nxt)
if (e[i].v!=f) dfs(e[i].v,u);
}
int main() {
n=read();
for (re int i=1;i<n;++i) {
int u=read(),v=read();
addEdge(u,v),addEdge(v,u);
}
for (re int i=1;i<=n;++i) c[i]=read();
for (re int i=1;i<=n;++i) w[i]=read();
T[0].mx[0]=T[1].mx[0]=-2e9; dfs(1,n+1);
Q=read();
while (Q--) {
int op=read(),u=read();
if (op==0) {
int rt=T[c[u]].findroot(u);
printf("%d\n",T[c[u]].mx[T[c[u]].ch[rt][1]]);
} else if (op==1) {
T[c[u]].cut(u,fa[u]),c[u]^=1,T[c[u]].link(u,fa[u]);
} else {
T[c[u]].access(u),T[c[u]].splay(u);
w[u]=read(); T[c[u]].pushup(u);
}
}
return 0;
}
4 条评论
真香我是这种人吗？
是的QTREE不应该写长链剖分球k级祖先吗
不会，告辞