题目描述
不久之前，Mirko建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了N座冰岛，并且提供观光服务。
当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。Mirko的旅行社遭受一次重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。
Mirko希望开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。这些冰岛从1到N标号。一开始时这些岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在[0, 1000]之间。你的程序需要处理以下三种命令：
- bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。
- penguins A X：将结点A对应的权值wA修改为X。
- excursion A B：如果结点A和结点B不连通，则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。
给出q个操作，要求在线处理所有操作。
输入输出格式
输入格式：第一行包含一个整数n(1<=n<=30000)，表示节点的数目。
第二行包含n个整数，第i个整数表示第i个节点初始时对应的权值。
第三行包含一个整数q(1<=n<=300000)，表示操作的数目。
以下q行，每行包含一个操作，操作的类别见题目描述。
任意时刻每个节点对应的权值都是1到1000的整数。
输出格式：输出所有bridge操作和excursion操作对应的输出，每个一行。
输入输出样例
输入样例#1：
复制
5
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
输出样例#1： 复制
4
impossible
yes
6
yes
yes
15
yes
15
16
说明
数据范围：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。
题解：放学前二十分钟准备切道水题，结果因为多写了个puts身败名裂……
其他没什么好说的了，基本和洛谷那道模板一模一样
代码如下：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 30030 #define lson ch[x][0] #define rson ch[x][1] using namespace std; int ch[N][2],f[N],v[N],sum[N],tag[N]; int not_root(int now) { register int x=f[now]; return lson==now||rson==now; } int push_up(int x) { sum[x]=sum[lson]+sum[rson]+v[x]; } int rev(int x) { swap(lson,rson); tag[x]^=1; } int push_down(int x) { if(tag[x]) { rev(lson); rev(rson); tag[x]^=1; } } int rotate(int x) { int y=f[x],z=f[y],kd=ch[y][1]==x,xs=ch[x][!kd]; if(not_root(y)) ch[z][ch[z][1]==y]=x; ch[x][!kd]=y; ch[y][kd]=xs; if(xs) f[xs]=y; f[y]=x; f[x]=z; push_up(y); } int push_all(int x) { if(not_root(x)) push_all(f[x]); push_down(x); } int splay(int x) { int y,z; push_all(x); while(not_root(x)) { y=f[x],z=f[y]; if(not_root(y)) (ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y); rotate(x); } push_up(x); } int access(int x) { for(int y=0;x;y=x,x=f[x]) { splay(x); rson=y; push_up(x); } } int make_root(int x) { access(x);splay(x); rev(x); } int split(int x,int y) { make_root(x); access(y);splay(y); } int find_root(int x) { access(x);splay(x); while(lson) { push_down(x); x=lson; } return x; } int link(int x,int y) { make_root(x); if(find_root(y)==x) return 0; f[x]=y; return 1; } int cut(int x,int y) { make_root(x); if(find_root(y)!=x||f[x]!=y||rson) return 0; f[x]=ch[y][0]=0; return 1; } int n,m; char op[30]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); } scanf("%d",&m); int from,to; while(m--) { scanf("%s",op); puts(""); if(op[0]=='e') { scanf("%d%d",&from,&to); make_root(from); if(find_root(to)!=from) { puts("impossible"); continue; } printf("%d ",sum[to]); } if(op[0]=='p') { scanf("%d%d",&from,&to); splay(from); v[from]=to; } if(op[0]=='b') { scanf("%d%d",&from,&to); if(link(from,to)) puts("yes"); else puts("no"); } } }