Description
不久之前，Mirko建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了N座冰岛，并且提供观光服务。当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。
Mirko的旅行社遭受一次重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。Mirko希望开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。
这些冰岛从1到N标号。一开始时这些岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在[0, 1000]之间。
你的程序需要处理以下三种命令：
1.”bridge A B”——在A与B之间建立一座大桥（A与B是不同的岛屿）。由于经费限制，这项命令被接受，当且仅当A与B不联通。若这项命令被接受，你的程序需要输出”yes”，之后会建造这座大桥。否则，你的程序需要输出”no”。
2.”penguins A X”——根据可靠消息，岛屿A此时的帝企鹅数量变为X。这项命令只是用来提供信息的，你的程序不需要回应。
3.”excursion A B”——一个旅行团希望从A出发到B。若A与B连通，你的程序需要输出这个旅行团一路上所能看到的帝企鹅数量（包括起点A与终点B），若不联通，你的程序需要输出”impossible”。
Input
第一行一个正整数N，表示冰岛的数量。
第二行N个范围[0, 1000]的整数，为每座岛屿初始的帝企鹅数量。
第三行一个正整数M，表示命令的数量。
接下来M行即命令，为题目描述所示。
Output
对于每个bridge命令与excursion命令，输出一行，为题目描述所示。
Sample Input
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
Sample Output
4
impossible
yes
6
yes
yes
15
yes
15
16
HINT
1<=N<=30000
1<=M<=100000
分析:
lct裸题
主体的操作已经会了
但是在解决具体问题的时候，操作就不明确了
简单总结一下
find(x)==find(y); //查找x，y是否联通
makeroot(n);
expose(x);
splay(x);
return size[ch[x][0]]; //查找一个点到根的距离
makeroot(x);
v[x]=y;
update(x); //优越的改变一个节点的值
makeroot(x);
expose(y);
spaly(y);
return sum[y]; //查找(x->y)路径上的值
//makeroot把x变成了树上目前的根
//在expose的时候，y会失去他的右儿子（深度比他大的节点）
//所以sum[y]记录的就是y到根上(x)的所有节点的值
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int N=35000;
int sum[N],lazy[N],ch[N][2],pre[N],q[N],v[N];
bool rev[N];
int n,m,a[N];
int get(int bh)
{
return ch[pre[bh]][0]==bh ? 0:1;
}
int isroot(int bh)
{
return ch[pre[bh]][0]!=bh&&ch[pre[bh]][1]!=bh;
}
void push(int bh)
{
if (bh&&rev[bh])
{
rev[bh]^=1;
if (ch[bh][0]) rev[ch[bh][0]]^=1;
if (ch[bh][1]) rev[ch[bh][1]]^=1;
swap(ch[bh][0],ch[bh][1]);
}
}
void update(int bh)
{
if (bh)
{
sum[bh]=v[bh];
if (ch[bh][0]) sum[bh]+=sum[ch[bh][0]];
if (ch[bh][1]) sum[bh]+=sum[ch[bh][1]];
}
return;
}
void rotate(int bh)
{
int fa=pre[bh];
int grand=pre[fa];
int wh=get(bh);
if (!isroot(fa)) ch[grand][ch[grand][0]==fa ? 0:1]=bh;
ch[fa][wh]=ch[bh][wh^1];
pre[ch[fa][wh]]=fa;
ch[bh][wh^1]=fa;
pre[fa]=bh;
pre[bh]=grand;
update(fa);
update(bh);
}
void splay(int bh)
{
int top=0;
q[++top]=bh;
for (int i=bh;!isroot(i);i=pre[i])
q[++top]=pre[i];
while (top) push(q[top--]);
for (int fa;!isroot(bh);rotate(bh))
if (!isroot(fa=pre[bh]))
rotate(get(bh)==get(fa) ? fa:bh);
}
void expose(int bh)
{
int t=0;
while (bh)
{
splay(bh);
ch[bh][1]=t;
update(bh); //产生了一个新儿子，需要update
t=bh;
bh=pre[bh];
}
}
void makeroot(int bh)
{
expose(bh);
splay(bh);
rev[bh]^=1;
}
void link(int x,int y)
{
makeroot(x);
pre[x]=y;
//splay(x);
}
void cut(int x,int y)
{
makeroot(x);
expose(y);
splay(y);
ch[y][0]=pre[x]=0;
}
int find(int x)
{
expose(x);
splay(x);
int t=x;
while (ch[t][0]) t=ch[t][0];
return t;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&sum[i]),v[i]=sum[i];
scanf("%d",&m);
char opt[15];
scanf("%c",&opt[0]);
for (int i=1;i<=m;i++)
{
int x,y;
scanf("%s",&opt);
scanf("%d%d",&x,&y);
if (opt[0]=='b')
{
if (find(x)==find(y))
printf("no
");
else
{
printf("yes
");
link(x,y);
}
}
else if (opt[0]=='p')
{
makeroot(x); //把它换到根上
v[x]=y; //这样就可以只改变一个节点的值
update(x);
}
else
{
if (find(x)!=find(y)) printf("impossible
");
else
{
makeroot(x); //
expose(y);
splay(y);
printf("%d
",sum[y]);
}
}
scanf("%c",&opt[0]);
}
return 0;
}