1180: [CROATIAN2009]OTOCI
Time Limit: 50 Sec Memory Limit: 162 MB
Submit: 1078 Solved: 662Description
给出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
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 5Sample Output
4
impossible
yes
6
yes
yes
15
yes
15
16HINT
Source
【分析】
LCT裸题。。
没有cut操作。。
嗯。。。还是要调试啊。。。
注意LCT是维护链的，，询问路径对LCT来说就是小菜一碟。。
不过之前维护子树的那题用LCT变成路径维护的感觉很强啊。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 30010 struct node
{
int son[],fa,w,sm;
bool rev;
node() {son[]=son[]=fa=w=sm=rev=;}
}tr[Maxn]; int q[Maxn],ql;
struct LCT
{
void upd(int x)
{
int lc=tr[x].son[],rc=tr[x].son[];
tr[x].sm=tr[lc].sm+tr[rc].sm+tr[x].w;
}
void push_down(int x)
{
int lc=tr[x].son[],rc=tr[x].son[];
if(tr[x].rev)
{
swap(tr[x].son[],tr[x].son[]);
tr[lc].rev^=;tr[rc].rev^=;
tr[x].rev=;
}
}
bool is_root(int x)
{
return tr[tr[x].fa].son[]!=x&&tr[tr[x].fa].son[]!=x;
}
void rot(int x)
{
int fa=tr[x].fa,yy=tr[fa].fa;
int w=tr[fa].son[]==x?:; if(!is_root(fa))
{
if(tr[yy].son[]==fa) tr[yy].son[]=x;
else tr[yy].son[]=x;
}tr[x].fa=yy; tr[tr[x].son[w]].fa=fa;
tr[fa].son[-w]=tr[x].son[w]; tr[x].son[w]=fa;
tr[fa].fa=x;
upd(fa);//upd(x);
}
void pre(int x)
{
ql=;
while(!is_root(x)) q[++ql]=x,x=tr[x].fa;
q[++ql]=x;
while(ql) push_down(q[ql--]);
}
void splay(int x)
{
pre(x);
while(!is_root(x))
{
int fa=tr[x].fa,yy=tr[fa].fa;
if(!is_root(fa))
{
if((tr[yy].son[]==fa)==(tr[fa].son[]==x)) rot(fa);
else rot(x);
}
rot(x);
}upd(x);
}
void access(int x)
{
int lt=;
while(x)
{
splay(x);
tr[x].son[]=lt;
upd(x);
lt=x;
x=tr[x].fa;
}
}
void make_root(int x)
{
access(x);
splay(x);
tr[x].rev^=;
}
void split(int x,int y)
{
make_root(x);
access(y);
splay(y);
}
int find_root(int x)
{
access(x);
splay(x);
while(tr[x].son[]) x=tr[x].son[];
return x;
}
bool cn(int x,int y)
{
return find_root(x)==find_root(y);
}
void link(int x,int y)
{
make_root(x);
tr[x].fa=y;
}
}LCT; char s[]; int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
tr[i].w=x;LCT.upd(x);
}
int q;
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%s%d%d",s,&x,&y);
if(s[]=='e')
{
if(!LCT.cn(x,y)) printf("impossible\n");
else
{
LCT.split(x,y);
printf("%d\n",tr[y].sm);
}
}
else if(s[]=='b')
{
if(!LCT.cn(x,y)) {printf("yes\n");LCT.link(x,y);}
else printf("no\n");
}
else
{
LCT.splay(x);
tr[x].w=y;LCT.upd(x);
}
}
return ;
}
2017-04-27 10:50:31