[文章目录]
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。
LCT，维护一个和就好了。闲的没事改了个数组版，发现并没有快多少。。。
算了，就写指针版吧。。。由于显得没事打完了，就贴数组版代码吧。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int fa,c[2],tur,w,sum;
void reverse(){swap(c[0],c[1]); tur^=1;}
void pushup();
void pushdown();
}t[30100];
void node::pushup(){sum=w+t[c[0]].sum+t[c[1]].sum;}
void node::pushdown()
{
if(tur)
{
if(c[0]) t[c[0]].reverse();
if(c[1]) t[c[1]].reverse();
tur=0;
}
}
int isr(int x){return (x!=t[t[x].fa].c[0])&&(x!=t[t[x].fa].c[1]);}
void rotate(int x)
{
if(isr(x)) return ;
int y=t[x].fa; int l=(x==t[y].c[1]),r=l^1;
t[y].c[l]=t[x].c[r]; t[t[x].c[r]].fa=y;
t[x].c[r]=y; t[x].fa=t[y].fa;
if(!isr(y)) t[t[y].fa].c[(y==t[t[y].fa].c[1])]=x;
t[y].fa=x; t[y].pushup(); t[x].pushup();
}
void pushall(int x)
{
if(!isr(x)) pushall(t[x].fa);
t[x].pushdown();
}
void splay(int x)
{
pushall(x);int y;
while(!isr(x))
{
y=t[x].fa;
if(!isr(y)) rotate((x==t[y].c[0])^(y==t[t[y].fa].c[0])?x:y);
rotate(x);
}
}
void access(int x)
{
int tmp=0;
while(x)
{
splay(x);
t[x].c[1]=tmp; t[x].pushup();
tmp=x; x=t[x].fa;
}
}
void moveroot(int x) {access(x); splay(x); t[x].reverse();}
void link(int x,int y)
{
moveroot(x); t[x].fa=y;
}
int same_tre(int x,int y)
{
while(t[x].fa) x=t[x].fa;
while(t[y].fa) y=t[y].fa;
return x==y;
}
int main()
{
int i,x,y,n,q;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d",&t[i].w); t[i].sum=t[i].w;
}
scanf("%d",&q); char sw[20];
while(q--)
{
scanf("%s%d%d",sw,&x,&y);
switch(sw[0])
{
case 'b':
{
if(same_tre(x,y)) puts("no");
else puts("yes"),link(x,y);
break;
}
case 'p':
{
t[x].w=y; t[x].pushup(); splay(x); break;
}
case 'e':
{
if(!same_tre(x,y)) puts("impossible");
else
{
moveroot(x); access(y); splay(y);
printf("%d\n",t[y].sum);
}
}
}
}
return 0;
}