[国家集训队]旅游
题目描述
Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。
Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。
现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。
输入格式
输入的第一行包含一个整数N，表示T 城中的景点个数。景点编号为 0…N − 1。
接下来N − 1 行，每行三个整数u、v 和w，表示有一条u 到v，使 Ray 愉悦度增加w 的桥。桥的编号为1…N − 1。|w| <= 1000。 输入的第N + 1 行包含一个整数M，表示Ray 的操作数目。
接下来有M 行，每行描述了一个操作，操作有如下五种形式：
C i w，表示Ray 对于经过第i 座桥的愉悦度变成了w。
N u v，表示Ray 对于经过景点u 到v 的路径上的每一座桥的愉悦度都变成原来的相反数。
SUM u v，表示询问从景点u 到v 所获得的总愉悦度。
MAX u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最大愉悦度。
MIN u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最小愉悦度。
测试数据保证，任意时刻，Ray 对于经过每一座桥的愉悦度的绝对值小于等于1000。
输出格式
对于每一个询问(操作S、MAX 和MIN)，输出答案。
输入输出样例
输入 #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
说明/提示
很容易的基础题哦>.<
不是很难，但是很恶心的一道树剖，聚聚帮我debug（在此感谢），QAQ，
这道题需要维护的信息挺多的，最大值，最小值，区间和，还有一个就是给出的是边的信息，然后树剖维护点，所以我们要把边变成点，怎么变呢？一般来说就两种办法，把边拆成两个点，或者把边用下面的点（深度深的点）来表示（点是唯一的，表示这条边），这样就可以了。所以我们写个裸的树剖就好了，写到自闭。QAQ（还是老老实实跟大佬写 LCT 吧）。这道题还有一个需要注意的点，就是对于两个点之间的桥，因为我们是用下面的点来表示这条边，所以更新的时候从上面的点下面那个点开始更新即可 updata(1,pos[x]+1,pos[y]);。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,a[N],b[N],c[N],h[N],f[N],sz[N],bl[N],pos[N],cnt=0;
int head[N],nex[N<<1],to[N<<1],tot;
struct node{
int l,r,add,sum,max,min;
}t[N<<2];
inline void add(int a,int b){
to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs1(int x){
sz[x]=1;
for(int i=head[x];i;i=nex[i]){
if(to[i]==f[x]) return ;
f[to[i]]=x; h[to[i]]=h[x]+1;
dfs1(to[i]); sz[x]+=sz[to[i]];
}
}
void dfs2(int x,int belong){
int k=0; pos[x]=++cnt; bl[x]=belong;
for(int i=head[x];i;i=nex[i])
if(h[to[i]]>h[x]&&sz[to[i]]>sz[k]) k=to[i];
if(!k) return ; dfs2(k,belong);
for(int i=head[x];i;i=nex[i])
if(h[to[i]]>h[x]&&to[i]!=k) dfs2(to[i],to[i]);
}
inline void push_up(int p){
t[p].max=max(t[p<<1].max,t[p<<1|1].max);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
t[p].min=min(t[p<<1].min, t[p<<1|1].min);
}
inline void push_down(int p){
if(t[p].add==-1){
swap(t[p<<1].max,t[p<<1].min);
swap(t[p<<1|1].max,t[p<<1|1].min);
t[p<<1].max*=-1; t[p<<1].min*=-1;
t[p<<1|1].max*=-1; t[p<<1|1].min*=-1;
t[p<<1].sum*=-1; t[p<<1|1].sum*=-1;
t[p<<1].add*=-1; t[p<<1|1].add*=-1;
t[p].add=1;
}
}
void build(int p,int l,int r){
t[p].l=l; t[p].r=r; t[p].add = 1;
if(l==r) return ; int mid=l+r>>1;
build(p<<1,l,mid); build(p<<1|1,mid+1,r);
}
void change(int p,int x,int v){
if(t[p].l==t[p].r){
t[p].sum=t[p].max=t[p].min=v; return ;
}
push_down(p); int mid=t[p].l+t[p].r>>1;
if(x<=mid) change(p<<1,x,v);
else change(p<<1|1,x,v);
push_up(p);
}
void updata(int p,int l,int r){
if(t[p].l==l&&t[p].r==r){
t[p].sum*=-1; swap(t[p].max,t[p].min);
t[p].max*=-1; t[p].min*=-1; t[p].add*=-1; return ;
}
push_down(p); int mid=t[p].l+t[p].r>>1;
if(r<=mid) updata(p<<1,l,r);
else if(l>mid) updata(p<<1|1,l,r);
else updata(p<<1,l,mid),updata(p<<1|1,mid+1,r);
push_up(p);
}
int ask(int p,int l,int r,int k){
if(t[p].l==l&&t[p].r==r) return (k?t[p].max:t[p].min);
int mid=t[p].l+t[p].r>>1;
push_down(p);
if(r<=mid) return ask(p<<1,l,r,k);
else if(l>mid) return ask(p<<1|1,l,r,k);
else{
if(k) return max(ask(p<<1,l,mid,k),ask(p<<1|1,mid+1,r,k));
else return min(ask(p<<1,l,mid,k),ask(p<<1|1,mid+1,r,k));
}
}
int asksum(int p,int l,int r){
if(t[p].l==l&&t[p].r==r) return t[p].sum;
int mid=t[p].l+t[p].r>>1;
push_down(p);
if(r<=mid) return asksum(p<<1,l,r);
else if(l>mid) return asksum(p<<1|1,l,r);
else return asksum(p<<1,l,mid)+asksum(p<<1|1,mid+1,r);
}
void flip(int x,int y){
while(bl[x]!=bl[y]){
if(h[bl[x]]<h[bl[y]]) swap(x,y);
updata(1,pos[bl[x]],pos[x]); x=f[bl[x]];
}
if(pos[x]==pos[y]) return ;
if(pos[x]>pos[y]) swap(x,y);
updata(1,pos[x]+1,pos[y]);
}
int query(int x,int y,int k){
int res=0x3f3f3f3f; if(k) res*=-1;
while(bl[x]!=bl[y]){
if(h[bl[x]]<h[bl[y]]) swap(x,y);
if(k) res=max(res,ask(1,pos[bl[x]],pos[x],1));
else res=min(res,ask(1,pos[bl[x]],pos[x],0));
x=f[bl[x]];
}
if(pos[x]==pos[y]) return res;
if(pos[x]>pos[y]) swap(x,y);
if(k) res=max(res,ask(1,pos[x]+1,pos[y],1));
else res=min(res,ask(1,pos[x]+1,pos[y],0));
return res;
}
int querysum(int x,int y){
int res=0;
while(bl[x]!=bl[y]){
if(h[bl[x]]<h[bl[y]]) swap(x,y);
res+=asksum(1,pos[bl[x]],pos[x]);
x=f[bl[x]];
}
if(pos[x]==pos[y]) return res;
if(pos[x]>pos[y]) swap(x,y);
res+=asksum(1,pos[x]+1,pos[y]);
return res;
}
signed main(){
scanf("%d",&n); build(1,1,n);
for(int i=1;i<n;i++){
scanf("%d %d %d",&a[i],&b[i],&c[i]); a[i]++; b[i]++;
add(a[i],b[i]); add(b[i],a[i]);
}
dfs1(1); dfs2(1,1);
for(int i=1;i<n;i++){
change(1,max(pos[a[i]],pos[b[i]]),c[i]);
}
scanf("%d",&m); char op[10];
while(m--){
int x,y; scanf("%s %d %d",op,&x,&y); x++; y++;
if(op[0]=='C') change(1,max(pos[a[x-1]],pos[b[x-1]]),y-1);
else if(op[0]=='N') flip(x,y);
else if(op[0]=='S') printf("%d\n",querysum(x,y));
else if(op[1]=='A') printf("%d\n",query(x,y,1));
else printf("%d\n",query(x,y,0));
}
return 0;
}
同程旅行工作强度 20人发布
