题目描述
乐忠于旅游,这次他来到了
城。
城是一个水上城市,一共有
个景点,有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本,
城的任意两个景点之间有且只有一条路径。换句话说,
城中只有
座桥。
发现,有些桥上可以看到美丽的景色,让人心情愉悦,但有些桥狭窄泥泞,令人烦躁。于是,他给每座桥定义一个愉悦度
,也就是说,
经过这座桥会增加
的愉悦度,这或许是正的也可能是负的。有时,
看待同一座桥的心情也会发生改变。
现在, 想让你帮他计算从
景点到
景点能获得的总愉悦度。有时,他还想知道某段路上最美丽的桥所提供的最大愉悦度,或是某段路上最糟糕的一座桥提供的最低愉悦度。
输入输出格式
输入格式:
输入的第一行包含一个整数,表示
城中的景点个数。景点编号为
。
接下来 行,每行三个整数
、
和
,表示有一条u 到
,使
愉悦度增加
的桥。桥的编号为
。
。 输入的第
行包含一个整数
,表示
的操作数目。
接下来有 行,每行描述了一个操作,操作有如下五种形式:
,表示
对于经过第
座桥的愉悦度变成了
。
,表示
对于经过景点
到
的路径上的每一座桥的愉悦度都变成原来的相反数。
,表示询问从景点
到
所获得的总愉悦度。
,表示询问从景点
到
的路径上的所有桥中某一座桥所提供的最大愉悦度。
,表示询问从景点
到
的路径上的所有桥中某一座桥所提供的最小愉悦度。
测试数据保证,任意时刻, 对于经过每一座桥的愉悦度的绝对值小于等于
。
输出格式:
对于每一个询问(操作、
和
),输出答案。
输入输出样例
输入样例#1:
3 0 1 1 1 2 2 8 SUM 0 2 MAX 0 2 N 0 1 SUM 0 2 MIN 0 2 C 1 3 SUM 0 2 MAX 0 2
输出样例#1:
3 2 1 -1 5 3
说明
很容易的基础题哦>.<
思路:如果说这道题是点权的话,那么就是一道树链剖分的板子题,但是,这道题是边权,那怎么办呢?可以发现,每个儿子只有一个父亲,那么我们就可以用这个儿子的点权来代替它与它父亲之间的边权,然后用树链剖分+线段树维护最大值,最小值和区间和即可。
代码:
#include #include #include #define maxn 200007 #define ls rt<<1 #define rs rt<<1|1 using namespace std; const int inf=0x7fffffff; int n,m,num,head[maxn],a[maxn],size[maxn],d[maxn],top[maxn]; int cnt,sum[maxn<<2],lazy[maxn<<2],maxx[maxn<<2],minn[maxn<<2]; int fa[maxn],id[maxn],zrj[maxn],son[maxn]; char s1[8]; inline int qread() { char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f; } struct node { int v,w,nxt; }e[maxn<<1]; inline void ct(int u, int v, int w) { e[++num].v=v; e[num].w=w; e[num].nxt=head[u]; head[u]=num; } void dfs1(int u) { size[u]=1; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(v!=fa[u]) { d[v]=d[u]+1; fa[v]=u; zrj[v]=e[i].w; dfs1(v); size[u]+=size[v]; if(size[v]>size[son[u]]) son[u]=v; } } } void dfs2(int u, int t) { id[u]=++cnt; top[u]=t; a[cnt]=zrj[u]; if(son[u]) dfs2(son[u],t); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(v!=fa[u]&&v!=son[u]) dfs2(v,v); } } inline void pushup(int rt) { sum[rt]=sum[ls]+sum[rs]; maxx[rt]=max(maxx[ls],maxx[rs]); minn[rt]=min(minn[ls],minn[rs]); } inline void pushdown(int rt) { if(lazy[rt]) { sum[ls]=-sum[ls],lazy[ls]^=1; sum[rs]=-sum[rs],lazy[rs]^=1; int t1=maxx[ls],t2=maxx[rs],s1=minn[ls],s2=minn[rs]; maxx[ls]=-s1,maxx[rs]=-s2,minn[ls]=-t1,minn[rs]=-t2; lazy[rt]=0; } } void build(int rt, int l, int r) { if(l==r) { sum[rt]=maxx[rt]=minn[rt]=a[l]; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); pushup(rt); } void add(int rt, int l, int r, int L, int val) { if(l==r) { sum[rt]=maxx[rt]=minn[rt]=val; return; } pushdown(rt); int mid=(l+r)>>1; if(L<=mid) add(ls,l,mid,L,val); else add(rs,mid+1,r,L,val); pushup(rt); } void modify(int rt, int l, int r, int L, int R) { if(L>r||R<l) return; if(L<=l&&r<=R) { sum[rt]=-sum[rt],lazy[rt]^=1; int t=maxx[rt],s=minn[rt]; maxx[rt]=-s,minn[rt]=-t; return; } int mid=(l+r)>>1; pushdown(rt); modify(ls,l,mid,L,R),modify(rs,mid+1,r,L,R); pushup(rt); } int csum(int rt, int l, int r, int L, int R) { if(L>r||R<l) return 0; if(L<=l&&r<=R) return sum[rt]; int mid=(l+r)>>1; pushdown(rt); return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R); } int cmax(int rt, int l, int r, int L, int R) { if(L>r||R<l) return -inf; if(L<=l&&r<=R) return maxx[rt]; int mid=(l+r)>>1,ans=-inf; pushdown(rt); if(L<=mid) ans=max(ans,cmax(ls,l,mid,L,R)); if(R>mid) ans=max(ans,cmax(rs,mid+1,r,L,R)); return ans; } int cmin(int rt, int l, int r, int L, int R) { if(L>r||R<l) return inf; if(L<=l&&r<=R) return minn[rt]; int mid=(l+r)>>1,ans=inf; pushdown(rt); if(L<=mid) ans=min(ans,cmin(ls,l,mid,L,R)); if(R>mid) ans=min(ans,cmin(rs,mid+1,r,L,R)); return ans; } void cal(int x, int y) { int fx=top[x],fy=top[y]; while(fx!=fy) { if(d[fx]<d[fy]) swap(x,y),swap(fx,fy); modify(1,1,cnt,id[fx],id[x]); x=fa[fx],fx=top[x]; } if(id[x]>id[y]) swap(x,y); modify(1,1,cnt,id[x]+1,id[y]); } int query_max(int x, int y) { int fx=top[x],fy=top[y],ans=-inf; while(fx!=fy) { if(d[fx]<d[fy]) swap(x,y),swap(fx,fy); ans=max(ans,cmax(1,1,cnt,id[fx],id[x])); x=fa[fx],fx=top[x]; } if(id[x]>id[y]) swap(x,y); ans=max(ans,cmax(1,1,cnt,id[x]+1,id[y])); return ans; } int query_min(int x, int y) { int fx=top[x],fy=top[y],ans=inf; while(fx!=fy) { if(d[fx]<d[fy]) swap(x,y),swap(fx,fy); ans=min(ans,cmin(1,1,cnt,id[fx],id[x])); x=fa[fx],fx=top[x]; } if(id[x]>id[y]) swap(x,y); ans=min(ans,cmin(1,1,cnt,id[x]+1,id[y])); return ans; } int query_sum(int x, int y) { int fx=top[x],fy=top[y],ans=0; while(fx!=fy) { if(d[fx]<d[fy]) swap(x,y),swap(fx,fy); ans+=csum(1,1,cnt,id[fx],id[x]); x=fa[fx],fx=top[x]; } if(id[x]>id[y]) swap(x,y); ans+=csum(1,1,cnt,id[x]+1,id[y]); return ans; } int main() { n=qread(); for(int i=1,u,v,w;i<n;++i) { u=qread()+1,v=qread()+1,w=qread(); ct(u,v,w);ct(v,u,w); } dfs1(1);dfs2(1,1);build(1,1,n); m=qread(); for(int i=1,x,y;i<=m;++i) { scanf("%s",s1);x=qread()+1,y=qread()+1; if(s1[0]=='C') add(1,1,n,id[x],y-1); if(s1[0]=='N') cal(x,y); if(s1[0]=='S') printf("%d\n",query_sum(x,y)); if(s1[1]=='I') printf("%d\n",query_min(x,y)); if(s1[1]=='A') printf("%d\n",query_max(x,y)); } return 0; }