本文主要是介绍BZOJ 1180 [CROATIAN2009]OTOCI Link Cut Trees，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作： 1、bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。 2、penguins A X：将结点A对应的权值wA修改为X。 3、excursion A B：如果结点A和结点B不连通，则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。给出q个操作，要求在线处理所有操作。数据范围：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。
Input
第一行包含一个整数n(1<=n<=30000)，表示节点的数目。第二行包含n个整数，第i个整数表示第i个节点初始时对应的权值。第三行包含一个整数q(1<=n<=300000)，表示操作的数目。以下q行，每行包含一个操作，操作的类别见题目描述。任意时刻每个节点对应的权值都是1到1000的整数。
Output
输出所有bridge操作和excursion操作对应的输出，每个一行。
Sample Input
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5
Sample Output
impossible
yes
6
yes
yes
15
yes
15
16
HINT
#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=30005;
int n;
struct LCT{int pre,son[2],sum,num;bool rev;
}tree[N];
bool isroot(int x){return tree[tree[x].pre].son[0]!=x &&tree[tree[x].pre].son[1]!=x;
}
void up(int x){if (x){int l=tree[x].son[0],r=tree[x].son[1];tree[x].sum=tree[x].num;if (l) tree[x].sum+=tree[l].sum;if (r) tree[x].sum+=tree[r].sum;}
}
void down(int x){if (x && tree[x].rev){int l=tree[x].son[0],r=tree[x].son[1];swap(tree[x].son[0],tree[x].son[1]);tree[l].rev^=1,tree[r].rev^=1,tree[x].rev^=1;}
}
void Rotate(int x){int y=tree[x].pre,z=tree[y].pre,l,r;if (tree[y].son[0]==x) l=0; else l=1;r=l^1;if (!isroot(y))if (tree[z].son[0]==y) tree[z].son[0]=x;else tree[z].son[1]=x;tree[x].pre=z,tree[y].pre=x;tree[y].son[l]=tree[x].son[r];tree[tree[x].son[r]].pre=y;tree[x].son[r]=y;up(y);
}
int stk[N];
void splay(int x){int top=1;stk[1]=x;for (int i=x;!isroot(i);i=tree[i].pre)stk[++top]=tree[i].pre;while (top) down(stk[top--]);while (!isroot(x)){int y=tree[x].pre,z=tree[y].pre;if (!isroot(y))if (tree[y].son[0]==x^tree[z].son[0]==y) Rotate(x);else Rotate(y);Rotate(x);}up(x);
}
void access(int x){for (int t=0;x;t=x,x=tree[x].pre)splay(x),tree[x].son[1]=t,up(x);
}
void makeroot(int x){access(x),splay(x);tree[x].rev^=1;
}
void split(int x,int y){makeroot(x);access(y),splay(y);
}
void link(int x,int y){makeroot(x);tree[x].pre=y;up(y);
}
int findroot(int x){access(x),splay(x);while (tree[x].son[0]) x=tree[x].son[0];return x;
}
bool sameset(int x,int y){return findroot(x)==findroot(y);
}
int querysum(int x,int y){split(x,y);return tree[y].sum;
}
int main(){n=read();for (int i=1;i<=n;i++)tree[i].num=read();int q=read(),x,y;char opt[15];while (q--){scanf("%s",opt);x=read(),y=read();if (opt[0]=='b')if (sameset(x,y)) puts("no");else puts("yes"),link(x,y);if (opt[0]=='p')tree[x].num=y,splay(x);if (opt[0]=='e')if (!sameset(x,y)) puts("impossible");else printf("%d\n",querysum(x,y));}return 0;
}这篇关于BZOJ 1180 [CROATIAN2009]OTOCI Link Cut Trees的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
