ACon#11#12

感觉有些奇怪，树剖部分和在P4315(也是树剖边转点）过了的代码进行了比对orz,暂时没发现什么问题，下载样例后发现MAX.MIN.SUM操作都是个别有问题，暂时也没发现和Cover的关系

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int n,m,rt=1;
int head[maxn],w[maxn],wt[maxn],tot;
int fa[maxn],son[maxn],id[maxn],dep[maxn],siz[maxn],top[maxn],cnt;

struct Edge
{
	int fr,to,nxt,w;
}e[maxn<<1];

struct Tree
{
	int mx,mn,sum;
	bool tag;
}st[maxn<<2];

void add(int u,int v,int w)
{
	e[++tot].to=v;
	e[tot].fr=u;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}

void dfs1(int u,int f,int depth)
{
	dep[u]=depth;
	fa[u]=f;
	siz[u]=1;
	int maxson=-1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(f==v) continue;
		dfs1(v,u,depth+1);
		w[v]=e[i].w;
		siz[u]+=siz[v];
		if(siz[v]>maxson) maxson=siz[v],son[u]=v;
	}
}

void dfs2(int u,int ltp)
{
	id[u]=++cnt;
	wt[cnt]=w[u];
	top[u]=ltp;
	if(!son[u]) return;
	dfs2(son[u],ltp);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	} 
}

void pushup(int now)
{
	st[now].sum=st[now<<1].sum+st[now<<1|1].sum;
	st[now].mn=min(st[now<<1].mn,st[now<<1|1].mn);
	st[now].mx=max(st[now<<1].mx,st[now<<1|1].mx);
}

void pushdown(int now)
{
	if(st[now].tag)
	{
		st[now<<1].sum=-st[now<<1].sum;
		swap(st[now<<1].mn,st[now<<1].mx);
		st[now<<1].mn=-st[now<<1].mn;
		st[now<<1].mx=-st[now<<1].mx;
		st[now<<1].tag^=1;;
		///
		st[now<<1|1].sum=-st[now<<1|1].sum;
		swap(st[now<<1|1].mn,st[now<<1|1].mx);
		st[now<<1|1].mn=-st[now<<1|1].mn;
		st[now<<1|1].mx=-st[now<<1|1].mx;
		st[now<<1|1].tag^=1;
		///
		st[now].tag=0;
	}
}

void build(int now,int l,int r)
{
	st[now].tag=0;
	if(l==r)
	{
		st[now].sum=wt[l];
		st[now].mn=wt[l];
		st[now].mx=wt[l];
		return;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	pushup(now);
}

void updateC(int now,int l,int r,int x,int w)
{
	if(l==r&&l==x)
	{
		st[now].sum=w;
		st[now].mn=w;
		st[now].mx=w;
		st[now].tag=0;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(now);
	if(x<=mid) updateC(now<<1,l,mid,x,w);
	else updateC(now<<1|1,mid+1,r,x,w);
	pushup(now);
}

void updateN(int now,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
	{
		st[now].sum=-st[now].sum;
		swap(st[now].mn,st[now].mx);
		st[now].mn=-st[now].mn;
		st[now].mx=-st[now].mx;
		st[now].tag^=1;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(now);
	if(x<=mid) updateN(now<<1,l,mid,x,y);
	if(y>mid) updateN(now<<1|1,mid+1,r,x,y);
	pushup(now);
}

int queryS(int now,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
	{
//		if(m==1986) cout<<"#st# "<<l<<' '<<r<<' '<<st[now].sum<<endl;
		return st[now].sum;
	}
		
	int mid=(l+r)>>1;
	int ans=0;
	pushdown(now);
	if(x<=mid) ans+=queryS(now<<1,l,mid,x,y);
	if(y>mid) ans+=queryS(now<<1|1,mid+1,r,x,y);
	return ans;
}

int queryMN(int now,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
		return st[now].mn;
	int mid=(l+r)>>1;
	int ans=inf;
	pushdown(now);
	if(x<=mid) ans=min(ans,queryMN(now<<1,l,mid,x,y));
	if(y>mid) ans=min(ans,queryMN(now<<1|1,mid+1,r,x,y));
	return ans;
}

int queryMX(int now,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
	{
		return st[now].mx;
	}
		
	int mid=(l+r)>>1;
	int ans=-inf;
	pushdown(now);
	if(x<=mid) ans=max(ans,queryMX(now<<1,l,mid,x,y));
	if(y>mid) ans=max(ans,queryMX(now<<1|1,mid+1,r,x,y));
	return ans;
}

void updN(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		updateN(1,1,n,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	updateN(1,1,n,id[x]+1,id[y]);
}

int qSum(int x,int y)
{
	int ans=0;
//	cout<<"#"<<m<<endl;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans+=queryS(1,1,n,id[top[x]],id[x]);
//		if(m==1986) cout<<"#"<<x<<' '<<y<<' '<<ans<<endl;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans+=queryS(1,1,n,id[x]+1,id[y]);
//	if(m==1986) cout<<"#"<<x<<' '<<y<<' '<<ans<<endl;
	return ans;
}

int qMax(int x,int y)
{
	int ans=-inf;
	
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans=max(ans,queryMX(1,1,n,id[top[x]],id[x]));
		
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans=max(ans,queryMX(1,1,n,id[x]+1,id[y]));

	return ans;
}

int qMin(int x,int y)
{
	int ans=inf;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans=min(ans,queryMN(1,1,n,id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans=min(ans,queryMN(1,1,n,id[x]+1,id[y]));
	return ans;
}

int main()
{
//	freopen("P1505_1_out.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u+1,v+1,w); add(v+1,u+1,w);
	}
	dfs1(rt,1,1);
	dfs2(rt,rt);
	build(1,1,n);
	scanf("%d",&m);
	char opt[5];
	int x,y;
	while(m--)
	{
		cin>>opt;
		scanf("%d%d",&x,&y);
		if(opt[0]=='C')
		{
			int u=e[x<<1].fr,v=e[x<<1].to;
			if(dep[u]>dep[v]) swap(u,v);
//			cout<<"#C# "<<v<<' '<<y<<endl;
			updateC(1,1,n,v,y);
		}
		if(opt[0]=='N')
			updN(x+1,y+1);
		if(opt[0]=='S')
			printf("%d\n",qSum(x+1,y+1));
		if(opt[1]=='A')
		{
			int ans=qMax(x+1,y+1);
			if(ans==-inf) printf("0\n");
			else printf("%d\n",ans);
		}
		if(opt[1]=='I')
		{
			int ans=qMin(x+1,y+1);
			if(ans==inf) printf("0\n");
			else printf("%d\n",ans);
		}
	}
	return 0;
}