| 记录编号 |
585372 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[国家集训队2011]旅游 |
最终得分 |
100 |
| 用户昵称 |
 ┭┮﹏┭┮ |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.158 s |
| 提交时间 |
2023-12-07 17:53:22 |
内存使用 |
83.94 MiB |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
int n,m;
struct made{
int ver,nx,ed;
}e[N<<1];
struct line{
int x,y;
}li[N];
int hd[N],tot,cnt;
int fa[N],size[N],dep[N],son[N];
int a[N],top[N],dfn[N],rnk[N];
struct Tree{
int l,r,sum,ma,mi,la;
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define ma(x) t[x].ma
#define mi(x) t[x].mi
#define la(x) t[x].la
}t[N<<3];
void pushup(int x){
sum(x) = sum(x<<1) + sum(x<<1|1);
ma(x) = max(ma(x<<1),ma(x<<1|1));
mi(x) = min(mi(x<<1),mi(x<<1|1));
}
void pushdown(int x){
if(!la(x))return;
la(x<<1) ^= 1,la(x<<1|1) ^= 1;
swap(ma(x<<1),mi(x<<1));
swap(ma(x<<1|1),mi(x<<1|1));
ma(x<<1) *= -1,mi(x<<1) *= -1;
ma(x<<1|1) *= -1,mi(x<<1|1) *= -1;
sum(x<<1) *= -1,sum(x<<1|1) *= -1;
la(x) = 0;
}
void build(int x,int l,int r){
l(x) = l,r(x) = r;
if(l == r){
sum(x) = mi(x) = ma(x) = a[rnk[l]];
return;
}
int mid = l + r >> 1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
void change(int x,int l,int z){
if(l(x) == r(x)){
sum(x) = mi(x) = ma(x) = z;
la(x) = 0;
return;
}
pushdown(x);
int mid = l(x) + r(x) >> 1;
if(l <= mid)change(x<<1,l,z);
if(l > mid)change(x<<1|1,l,z);
pushup(x);
}
void negative(int x,int l,int r){
if(l <= l(x) && r(x) <= r){
swap(mi(x),ma(x));
mi(x) *= -1,ma(x) *= -1;
sum(x) *= -1;
la(x) ^= 1;
pushdown(x);
return;
}
pushdown(x);
int mid = l(x) + r(x) >> 1;
if(l <= mid)negative(x<<1,l,r);
if(r > mid)negative(x<<1|1,l,r);
pushup(x);
}
int asksum(int x,int l,int r){
if(l <= l(x) && r(x) <= r)return sum(x);
pushdown(x);
int mid = l(x) + r(x) >> 1,ans = 0;
if(l <= mid)ans += asksum(x<<1,l,r);
if(r > mid)ans += asksum(x<<1|1,l,r);
return ans;
}
int askmax(int x,int l,int r){
if(l <= l(x) && r(x) <= r)return ma(x);
pushdown(x);
int mid = l(x) + r(x) >> 1,ans = INT_MIN;
if(l <= mid)ans = max(ans,askmax(x<<1,l,r));
if(r > mid)ans = max(ans,askmax(x<<1|1,l,r));
return ans;
}
int askmin(int x,int l,int r){
if(l <= l(x) && r(x) <= r)return mi(x);
pushdown(x);
int mid = l(x) + r(x) >> 1,ans = INT_MAX;
if(l <= mid)ans = min(ans,askmin(x<<1,l,r));
if(r > mid)ans = min(ans,askmin(x<<1|1,l,r));
return ans;
}
//--------------------
void add(int x,int y,int z){
tot++;
e[tot].nx = hd[x],e[tot].ver = y,e[tot].ed = z,hd[x] = tot;
}
void dfs1(int x){
size[x] = 1;
for(int i = hd[x];i;i = e[i].nx){
int y = e[i].ver;
if(dep[y])continue;
dep[y] = dep[x] + 1;
fa[y] = x,a[y] = e[i].ed;
dfs1(y);
size[x] += size[y];
if(!son[x] || size[y] > size[son[x]])son[x] = y;
}
}
void dfs2(int x,int t){
dfn[x] = ++cnt;
rnk[cnt] = x;
top[x] = t;
if(!son[x])return;
dfs2(son[x],t);
for(int i = hd[x];i;i = e[i].nx){
int y = e[i].ver;
if(y != fa[x] && y != son[x])dfs2(y,y);
}
}
void opp(int x,int y){
int fx = top[x],fy = top[y];
while(fx != fy){
if(dep[fx] < dep[fy])swap(x,y),swap(fx,fy);
negative(1,dfn[fx],dfn[x]);
x = fa[fx];fx = top[x];
}
if(x == y)return;
if(dep[x] > dep[y])swap(x,y);
negative(1,dfn[x]+1,dfn[y]);
}
int calsum(int x,int y){
int fx = top[x],fy = top[y],ans = 0;
while(fx != fy){
if(dep[fx] < dep[fy])swap(x,y),swap(fx,fy);
ans += asksum(1,dfn[fx],dfn[x]);
x = fa[fx];fx = top[x];
}
if(x == y)return ans;
if(dep[x] > dep[y])swap(x,y);
ans += asksum(1,dfn[x]+1,dfn[y]);
return ans;
}
int calmax(int x,int y){
int fx = top[x],fy = top[y],ans = INT_MIN;
while(fx != fy){
if(dep[fx] < dep[fy])swap(x,y),swap(fx,fy);
ans = max(ans,askmax(1,dfn[fx],dfn[x]));
x = fa[fx],fx = top[x];
}
if(x == y)return ans;
if(dep[x] > dep[y])swap(x,y);
ans = max(ans,askmax(1,dfn[x]+1,dfn[y]));
return ans;
}
int calmin(int x,int y){
int fx = top[x],fy = top[y],ans = INT_MAX;
while(fx != fy){
if(dep[fx] < dep[fy])swap(x,y),swap(fx,fy);
ans = min(ans,askmin(1,dfn[fx],dfn[x]));
x = fa[fx];fx = top[x];
}
if(x == y)return ans;
if(dep[x] > dep[y])swap(x,y);
ans = min(ans,askmin(1,dfn[x]+1,dfn[y]));
return ans;
}
int main(){
freopen("nt2011_travel.in","r",stdin);
freopen("nt2011_travel.out","w",stdout);
scanf("%d",&n);
for(int i = 1;i < n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x++,y++;
add(x,y,z);add(y,x,z);
li[i].x = x,li[i].y = y;
}
dep[1] = 1;
dfs1(1);
dfs2(1,1);
build(1,1,n);
scanf("%d",&m);
for(int i = 1;i <= m;i++){
char c[10];int x,y;
scanf("%s%d%d",c,&x,&y);
if(c[0] == 'C'){
x = dep[li[x].x] > dep[li[x].y]?li[x].x:li[x].y;
change(1,dfn[x],y);
}
else if(c[0] == 'N')opp(x+1,y+1);
else if(c[0] == 'S')printf("%d\n",calsum(x+1,y+1));
else if(c[1] == 'A')printf("%d\n",calmax(x+1,y+1));
else printf("%d\n",calmin(x+1,y+1));
}
return 0;
}