【hdu4010】 Query on The Trees

时间:2022-07-12 01:16:29

http://acm.hdu.edu.cn/showproblem.php?pid=4010 (题目链接)

题意

  link cut tree板子

Solution

  link cut tree

细节

  注意第二个询问切的是什么

代码

// hdu4010
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define LL long long
#define inf 2147483647
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=300010;
int val[maxn],tag[maxn],rev[maxn],fa[maxn],mx[maxn],tr[maxn][2];
int n,m; void Init() {
memset(tag,0,sizeof(tag));memset(fa,0,sizeof(fa));
memset(rev,0,sizeof(rev));memset(tr,0,sizeof(tr));
mx[0]=-inf;
}
void pushup(int x) {
mx[x]=max(mx[tr[x][0]],mx[tr[x][1]]);
mx[x]=max(mx[x],val[x]);
}
void pushdown(int x) {
int l=tr[x][0],r=tr[x][1];
if (tr[fa[x]][0]==x || tr[fa[x]][1]==x) pushdown(fa[x]);
if (rev[x]) {
swap(tr[x][0],tr[x][1]);
rev[l]^=1;rev[r]^=1;rev[x]^=1;
}
if (tag[x]) {
if (l) tag[l]+=tag[x],mx[l]+=tag[x],val[l]+=tag[x];
if (r) tag[r]+=tag[x],mx[r]+=tag[x],val[r]+=tag[x];
tag[x]=0;
}
}
void rotate(int x) {
int y=fa[x],z=fa[y],l,r;
if (tr[y][0]==x) l=0;else l=1;r=l^1;
if (tr[fa[y]][0]==y || tr[fa[y]][1]==y) tr[z][tr[z][1]==y]=x;
fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
tr[y][l]=tr[x][r];tr[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x) {
pushdown(x);
while (tr[fa[x]][0]==x || tr[fa[x]][1]==x) {
int y=fa[x],z=fa[y];
if (tr[z][0]==y || tr[z][1]==y) {
if (tr[y][0]==x ^ tr[z][0]==y) rotate(x);
else rotate(y);
}
rotate(x);
}
}
int find(int x) {
while (fa[x]) x=fa[x];
return x;
}
void access(int x) {
for (int y=0;x;y=x,x=fa[x])
splay(x),tr[x][1]=y,pushup(x);
}
void makeroot(int x) {
access(x);splay(x);rev[x]^=1;
}
void link(int x,int y) {
makeroot(x);fa[x]=y;
}
void cut(int x,int y) {
makeroot(x);access(y);splay(y);
tr[y][0]=fa[tr[y][0]]=0;//注意这个地方,要求断的是y和其祖先的边
pushup(y);
}
void modify(int x,int y,int w) {
makeroot(x);access(y);splay(y);
tag[y]+=w;mx[y]+=w;val[y]+=w;
}
int query(int x,int y) {
makeroot(x);access(y);splay(y);
return mx[y];
}
int main() {
while (scanf("%d",&n)!=EOF) {
Init();
for (int u,v,i=1;i<n;i++) {
scanf("%d%d",&u,&v);
link(u,v);
}
for (int i=1;i<=n;i++) scanf("%d",&val[i]),mx[i]=val[i];
scanf("%d",&m);
for (int op,x,y,w,i=1;i<=m;i++) {
scanf("%d",&op);
if (op==1) {
scanf("%d%d",&x,&y);
if (find(x)==find(y)) {puts("-1");continue;}
link(x,y);
}
if (op==2) {
scanf("%d%d",&x,&y);
if (x==y || find(x)!=find(y)) {puts("-1");continue;}
cut(x,y);
}
if (op==3) {
scanf("%d%d%d",&w,&x,&y);
if (find(x)!=find(y)) {puts("-1");continue;}
modify(x,y,w);
}
if (op==4) {
scanf("%d%d",&x,&y);
if (find(x)!=find(y)) {puts("-1");continue;}
printf("%d\n",query(x,y));
}
}
puts("");
}
return 0;
}