题目链接：长跑
这道题要求维护一张图，有三个操作：
1.在(u)，(v)之间加入一条边；
2.把(u)点的权值修改为(v)；
3.要求把所有边定向，询问从(u)到(v)的路径可以经过的最大点权和。路径可以是非简单路径，同一个点权值只算一次。
首先可以发现如果形成了一个边双，那么这个边双内的所有点的贡献就都可以一起算上了。所以每次加边的时候，如果形成了一个边双，那么就暴力把他们给合并了，每次就只需要询问路径点权和了。这个用(LCT)维护即可。缩点的时候可以用并查集维护一下每个点缩点后所属的点。复杂度(O(malpha(n)log n))
还有一种树链剖分的做法。我们可以先离线构出树，那么同理，如果某次操作后出现了边双，我们就可以直接把这些点的权值集中到(lca)，其余位置清(0)。用(LCT)实现这个也是可以的，但是用树链剖分套树状数组会更快。复杂度(O(mlog n))或者(O(mlog^2 n))
下面贴代码(第一种做法)：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define isroot(x) (x!=s[fa[x]][0] && x!=s[fa[x]][1])
#define maxn 150010
using namespace std;
typedef long long llg;
int n,m,val[maxn],sumv[maxn],a[maxn];
int fa[maxn],s[maxn][2],d[maxn];
int f1[maxn],f2[maxn],s1[maxn],s2[maxn];
bool rev[maxn];
int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
}
int fi1(int x){return f1[f1[x]]==f1[x]?f1[x]:f1[x]=fi1(f1[x]);}
int fi2(int x){return f2[f2[x]]==f2[x]?f2[x]:f2[x]=fi2(f2[x]);}
void update(int u){sumv[u]=sumv[s[u][0]]+sumv[s[u][1]]+val[u];}
void R(int u){
int p=fa[u],g=fa[p];
bool l=(u==s[p][1]),r=!l;
if(!isroot(p)) s[g][p==s[g][1]]=u;
fa[s[u][r]]=p; s[p][l]=s[u][r];
s[u][r]=p; fa[p]=u; fa[u]=g;
update(p); update(u);
}
void splay(int u){
int ld=0; d[ld=1]=u;
for(int i=u;!isroot(i);i=fa[i]) d[++ld]=fa[i];
for(int i=ld,x;x=d[i],i;i--)
if(rev[x]){
rev[s[x][0]]^=1,rev[s[x][1]]^=1;
swap(s[x][0],s[x][1]); rev[x]=0;
}
while(!isroot(u)){
int p=fa[u],g=fa[p];
if(!isroot(p)){
if((u==s[p][1])^(p==s[g][1])) R(u);
else R(p);
}
R(u);
}
}
void access(int u){
for(int t=0;u;t=u,u=fa[u]=fi1(fa[u]))
splay(u),s[u][1]=t,update(u);
}
void makert(int u){access(u); splay(u); rev[u]^=1;}
void merge(int x,int y){
x=fi1(x),y=fi1(y);
if(s1[x]>s1[y]) x^=y^=x^=y;
f1[x]=y; s1[y]+=s1[x];
}
void dfs(int u,int fa){
if(u!=fa) merge(u,fa);
if(s[u][0]) dfs(s[u][0],u);
if(s[u][1]) dfs(s[u][1],u);
}
int main(){
File("a");
n=getint(),m=getint();
for(int i=1;i<=n;i++){
a[i]=val[i]=sumv[i]=getint();
f1[i]=f2[i]=i,s1[i]=s2[i]=1;
}
while(m--){
int op=getint(),u=getint(),v=getint();
if(op==1){
if(fi2(u)!=fi2(v)){
makert(fi1(u)),fa[fi1(u)]=fi1(v);
u=fi2(u),v=fi2(v);
if(s2[u]>s2[v]) u^=v^=u^=v;
s2[v]+=s2[u]; f2[u]=v;
}
else if(fi1(u)!=fi1(v)){
makert(u=fi1(u)); v=fi1(v);
access(v),splay(v); dfs(v,v); splay(v=fi1(v));
val[v]=sumv[v]; s[v][0]=s[v][1]=0;
}
}
else if(op==2){
int x=fi1(u); makert(x); val[x]+=v-a[u];
sumv[x]+=v-a[u]; a[u]=v;
}
else if(op==3)
if(fi2(u)!=fi2(v)) printf("-1
");
else{
u=fi1(u); v=fi1(v);
makert(u),access(v),splay(v);
printf("%d
",sumv[v]);
}
}
return 0;
}