裸链剖。
这大概是我第一份两百行左右的代码吧。
然而我把题看错了233333333调了将近两天。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 100050
#define maxe 300050
using namespace std;
struct edge
{
int v,w,nxt;
}e[maxe];
struct edge_
{
int u,v,w;
}eg[maxe];
char s[];
int n,x,y,z,g[maxv],nume=,nume_=,m;
int dis[maxv],w[maxv],top[maxv],fath[maxv],size[maxv],son[maxv],cnt=,tot=,c[maxv];
int ls[maxv<<],rs[maxv<<],lazy[maxv<<],sum[maxv<<],mx[maxv<<],mn[maxv<<],root;
void addedge(int u,int v,int w)
{
e[++nume].v=v;
e[nume].w=w;
e[nume].nxt=g[u];
g[u]=nume;
}
void addedge_(int u,int v,int w)
{
eg[++nume_].u=u;
eg[nume_].v=v;
eg[nume_].w=w;
}
void dfs1(int x,int father)
{
size[x]=;son[x]=;
for (int i=g[x];i;i=e[i].nxt)
{
int v=e[i].v;
if (v!=father)
{
fath[v]=x;dis[v]=dis[x]+;
dfs1(v,x);
size[x]+=size[v];
if (size[v]>size[son[x]]) son[x]=v;
}
}
}
void dfs2(int x,int father)
{
top[x]=father;w[x]=++cnt;
if (son[x]!=) dfs2(son[x],father);
for (int i=g[x];i;i=e[i].nxt)
{
int v=e[i].v;
if (v!=fath[x])
{
if (v!=son[x]) dfs2(v,v);
c[w[v]]=e[i].w;
}
}
}
void pushup(int now)
{
sum[now]=sum[ls[now]]+sum[rs[now]];
mx[now]=max(mx[ls[now]],mx[rs[now]]);
mn[now]=min(mn[ls[now]],mn[rs[now]]);
}
void build(int &now,int left,int right)
{
now=++tot;lazy[now]=;
if (left==right)
{
sum[now]=mn[now]=mx[now]=c[left];
return;
}
int mid=(left+right)>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
pushup(now);
}
void pushdown(int now,int left,int right)
{
int r1,r2;
if (lazy[now]==)
{
sum[ls[now]]=-sum[ls[now]];sum[rs[now]]=-sum[rs[now]];
r1=mn[ls[now]];r2=mx[ls[now]];mn[ls[now]]=-r2;mx[ls[now]]=-r1;
r1=mn[rs[now]];r2=mx[rs[now]];mn[rs[now]]=-r2;mx[rs[now]]=-r1;
lazy[ls[now]]^=;lazy[rs[now]]^=;
lazy[now]=;
}
}
void modify(int now,int left,int right,int l,int r,int p,int type)
{
pushdown(now,left,right);
if ((left==l) && (right==r))
{
if (type==)
{
sum[now]=p;
mx[now]=p;mn[now]=p;
return;
}
else
{
lazy[now]^=;
sum[now]=-sum[now];
int r1,r2;r1=mn[now];r2=mx[now];
mn[now]=-r2;mx[now]=-r1;
return;
}
}
int mid=(left+right)>>;
if (r<=mid) modify(ls[now],left,mid,l,r,p,type);
else if (l>=mid+) modify(rs[now],mid+,right,l,r,p,type);
else
{
modify(ls[now],left,mid,l,mid,p,type);
modify(rs[now],mid+,right,mid+,r,p,type);
}
pushup(now);
}
int ask(int now,int left,int right,int l,int r,int type)
{
pushdown(now,left,right);
if ((left==l) && (right==r))
{
if (type==) return sum[now];
else if (type==) return mx[now];
else return mn[now];
}
int mid=(left+right)>>;
if (r<=mid) return ask(ls[now],left,mid,l,r,type);
else if (l>=mid+) return ask(rs[now],mid+,right,l,r,type);
else
{
if (type==) return ask(ls[now],left,mid,l,mid,type)+ask(rs[now],mid+,right,mid+,r,type);
else if (type==) return max(ask(ls[now],left,mid,l,mid,type),ask(rs[now],mid+,right,mid+,r,type));
else return min(ask(ls[now],left,mid,l,mid,type),ask(rs[now],mid+,right,mid+,r,type));
}
}
void work()
{
scanf("%d%d",&x,&y);
x++;y++;
int f1=top[x],f2=top[y];
if (s[]=='N')
{
while (f1!=f2)
{
if (dis[f1]<dis[f2]) {swap(f1,f2);swap(x,y);}
modify(root,,cnt,w[f1],w[x],,);
x=fath[f1];f1=top[x];
}
if (x!=y)
{
if (dis[x]>dis[y]) swap(x,y);
modify(root,,cnt,w[son[x]],w[y],,);
}
}
else if (s[]=='S')
{
int ans=;
while (f1!=f2)
{
if (dis[f1]<dis[f2]) {swap(f1,f2);swap(x,y);}
ans+=ask(root,,cnt,w[f1],w[x],);
x=fath[f1];f1=top[x];
}
if (x!=y)
{
if (dis[x]>dis[y]) swap(x,y);
ans+=ask(root,,cnt,w[son[x]],w[y],);
}
printf("%d\n",ans);
}
else if ((s[]=='M') && (s[]=='A'))
{
int ans=0xefefefef;
while (f1!=f2)
{
if (dis[f1]<dis[f2]) {swap(f1,f2);swap(x,y);}
ans=max(ans,ask(root,,cnt,w[f1],w[x],));
x=fath[f1];f1=top[x];
}
if (x!=y)
{
if (dis[x]>dis[y]) swap(x,y);
ans=max(ans,ask(root,,cnt,w[son[x]],w[y],));
}
printf("%d\n",ans);
}
else
{
int ans=0x3f3f3f3f;
while (f1!=f2)
{
if (dis[f1]<dis[f2]) {swap(f1,f2);swap(x,y);}
ans=min(ans,ask(root,,cnt,w[f1],w[x],));
x=fath[f1];f1=top[x];
}
if (x!=y)
{
if (dis[x]>dis[y]) swap(x,y);
ans=min(ans,ask(root,,cnt,w[son[x]],w[y],));
}
printf("%d\n",ans);
}
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n-;i++)
{
scanf("%d%d%d",&x,&y,&z);
x++;y++;
addedge(x,y,z);
addedge(y,x,z);
addedge_(x,y,z);
}
dfs1(,);
dfs2(,);
build(root,,cnt);
scanf("%d",&m);
for (int i=;i<=m;i++)
{
scanf("%s",s);
if (s[]=='C')
{
scanf("%d%d",&x,&y);
int u,v;
u=eg[x].u;v=eg[x].v;
if (fath[u]==v) modify(root,,cnt,w[u],w[u],y,);
else modify(root,,cnt,w[v],w[v],y,);
}
else work();
}
return ;
}