题目
给出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。
输入格式
第一行包含一个整数n(1<=n<=30000)，表示节点的数目。第二行包含n个整数，第i个整数表示第i个节点初始时对应的权值。第三行包含一个整数q(1<=n<=300000)，表示操作的数目。以下q行，每行包含一个操作，操作的类别见题目描述。任意时刻每个节点对应的权值都是1到1000的整数。
输出格式
输出所有bridge操作和excursion操作对应的输出，每个一行。
输入样例
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
输出样例
4
impossible
yes
6
yes
yes
15
yes
15
16
题解
LCT板题
但蒟蒻opt[0]打成了opt[1]查了一个中午QAQ
对着黄学长代码还是学会了更加简化的LCT代码
没白弄
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define isrt(u) !(e[e[u].f].ch[0] == u || e[e[u].f].ch[1] == u)
#define isr(u) (e[e[u].f].ch[1] == u)
#define ls e[u].ch[0]
#define rs e[u].ch[1]
using namespace std;
const int maxn = 30005,maxm = 100005,INF = 1000000000;
inline int RD(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
return out * flag;
}
int N,M;
char opt[20];
struct node{int f,ch[2],w,sum,rev;}e[maxn];
void pup(int u){e[u].sum = e[ls].sum + e[u].w + e[rs].sum;}
void pd(int u){
if (e[u].rev){
swap(ls,rs);
e[ls].rev ^= 1; e[rs].rev ^= 1; e[u].rev ^= 1;
}
}
void push_down(int u){
if (!isrt(u)) push_down(e[u].f);
pd(u);
}
void spin(int u){
int s = isr(u),fa = e[u].f;
e[u].f = e[fa].f; if (!isrt(fa)) e[e[fa].f].ch[isr(fa)] = u;
e[fa].ch[s] = e[u].ch[s ^ 1]; if (e[u].ch[s ^ 1]) e[e[u].ch[s ^ 1]].f = fa;
e[fa].f = u; e[u].ch[s ^ 1] = fa;
pup(fa); pup(u);
}
void splay(int u){
push_down(u);
for (; !isrt(u); spin(u))
if (!isrt(e[u].f)) spin((isr(u) ^ isr(e[u].f)) ? u : e[u].f);
}
void Access(int u){
for (int v = 0; u; u = e[v = u].f)
splay(u),e[u].ch[1] = v,pup(u);
}
void Make_root(int u){Access(u); splay(u); e[u].rev ^= 1;}
int Getrt(int u){
Access(u); splay(u);
while (ls) u = ls;
return u;
}
void Link(int u,int v){
Make_root(u); e[u].f = v;
}
int Getsum(int u,int v){
Make_root(u); Access(v); splay(v);
return e[v].sum;
}
void solve1(int u,int v){
if (Getrt(u) == Getrt(v)) puts("no");
else puts("yes"),Link(u,v);
}
void solve2(int u,int v){
Make_root(u);
e[u].w = v; pup(u);
}
void solve3(int u,int v){
if (Getrt(u) == Getrt(v)) printf("%d
",Getsum(u,v));
else puts("impossible");
}
int main(){
N = RD(); REP(i,N) e[i].w = e[i].sum = RD();
M = RD(); int u,v;
while (M--){
scanf("%s",opt); u = RD(); v = RD();
if (opt[0] == 'b') solve1(u,v);
else if (opt[0] == 'p') solve2(u,v);
else solve3(u,v);
}
return 0;
}