| 记录编号 |
438424 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[国家集训队2011]旅游 |
最终得分 |
100 |
| 用户昵称 |
 Hzoi_Mafia |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.139 s |
| 提交时间 |
2017-08-16 06:44:16 |
内存使用 |
11.61 MiB |
显示代码纯文本
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
inline int read(){
int sum(0),f(1);
char ch(getchar());
for(;ch<'0'||ch>'9';ch=getchar())
if(ch=='-')
f=-1;
for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
return sum*f;
}
struct edge{
int s,e,w;
edge *n;
edge():s(0),e(0),w(0),n(NULL){}
}a[200005],*pre[100005];
int tot;
inline void insert(int s,int e,int w){
a[++tot].s=s;
a[tot].e=e;
a[tot].w=w;
a[tot].n=pre[s];
pre[s]=&a[tot];
}
int n,m;
int w[100005];
int dep[100005],fa[100005],son[100005],size[100005];
inline void dfs1(int u){
son[u]=0,size[u]=1;
for(edge *i=pre[u];i;i=i->n){
int e(i->e);
if(e!=fa[u]){
fa[e]=u;
dep[e]=dep[u]+1;
w[e]=i->w;
dfs1(e);
size[u]+=size[e];
if(size[e]>size[son[u]])
son[u]=e;
}
}
}
int cnt;
int id[100005],top[100005],pos[100005];
inline void dfs2(int u,int rt){
top[u]=rt;
id[u]=++cnt;
pos[cnt]=u;
if(son[u])
dfs2(son[u],rt);
for(edge *i=pre[u];i;i=i->n){
int e(i->e);
if(e!=fa[u]&&e!=son[u])
dfs2(e,e);
}
}
int sum[400005],mx[400005],mn[400005],lazy[400005];
inline void pushup(int i){
sum[i]=sum[i<<1]+sum[i<<1|1];
mx[i]=max(mx[i<<1],mx[i<<1|1]);
mn[i]=min(mn[i<<1],mn[i<<1|1]);
}
inline void pushdown(int i){
if(lazy[i]){
sum[i<<1]=-sum[i<<1],sum[i<<1|1]=-sum[i<<1|1];
int x,n;
mx[i<<1]=-mx[i<<1],mn[i<<1]=-mn[i<<1];
swap(mx[i<<1],mn[i<<1]);
mx[i<<1|1]=-mx[i<<1|1],mn[i<<1|1]=-mn[i<<1|1];
swap(mx[i<<1|1],mn[i<<1|1]);
lazy[i<<1]^=1;
lazy[i<<1|1]^=1;
lazy[i]=0;
}
}
inline void build(int l,int r,int i){
if(l==r){
sum[i]=mx[i]=mn[i]=w[pos[l]];
return;
}
int mid((l+r)>>1);
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
pushup(i);
}
inline void revs(int ll,int rr,int l,int r,int i){
if(ll<=l&&r<=rr){
lazy[i]^=1;
// if(lazy[i]){
sum[i]=-sum[i];
mx[i]=-mx[i];
mn[i]=-mn[i];
swap(mx[i],mn[i]);
// }
return;
}
pushdown(i);
int mid((l+r)>>1);
if(ll<=mid)
revs(ll,rr,l,mid,i<<1);
if(mid<rr)
revs(ll,rr,mid+1,r,i<<1|1);
pushup(i);
}
inline void update(int pos,int w,int l,int r,int i){
if(l==r){
sum[i]=mx[i]=mn[i]=w;
return;
}
pushdown(i);
int mid((l+r)>>1);
if(pos<=mid)
update(pos,w,l,mid,i<<1);
else
update(pos,w,mid+1,r,i<<1|1);
pushup(i);
}
inline int query_sum(int ll,int rr,int l,int r,int i){
if(ll<=l&&r<=rr)
return sum[i];
pushdown(i);
int mid((l+r)>>1),ret(0);
if(ll<=mid)
ret+=query_sum(ll,rr,l,mid,i<<1);
if(mid<rr)
ret+=query_sum(ll,rr,mid+1,r,i<<1|1);
return ret;
}
inline int query_mx(int ll,int rr,int l,int r,int i){
if(ll<=l&&r<=rr)
return mx[i];
pushdown(i);
int mid((l+r)>>1),ret(-0x7fffffff);
if(ll<=mid)
ret=max(ret,query_mx(ll,rr,l,mid,i<<1));
if(mid<rr)
ret=max(ret,query_mx(ll,rr,mid+1,r,i<<1|1));
return ret;
}
inline int query_mn(int ll,int rr,int l,int r,int i){
if(ll<=l&&r<=rr)
return mn[i];
pushdown(i);
int mid((l+r)>>1),ret(0x7fffffff);
if(ll<=mid)
ret=min(ret,query_mn(ll,rr,l,mid,i<<1));
if(mid<rr)
ret=min(ret,query_mn(ll,rr,mid+1,r,i<<1|1));
return ret;
}
char op[5];
inline void change(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
revs(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
revs(id[x]+1,id[y],1,n,1);
}
inline int q_sum(int x,int y){
int ret(0);
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ret+=query_sum(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
ret+=query_sum(id[x]+1,id[y],1,n,1);
return ret;
}
inline int q_mx(int x,int y){
int ret(-0x7fffffff);
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ret=max(ret,query_mx(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
ret=max(ret,query_mx(id[x]+1,id[y],1,n,1));
return ret;
}
inline int q_mn(int x,int y){
int ret(0x7fffffff);
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ret=min(ret,query_mn(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
ret=min(ret,query_mn(id[x]+1,id[y],1,n,1));
return ret;
}
int root(0x7fffffff),realn;
inline int gg(){
freopen("nt2011_travel.in","r",stdin);
freopen("nt2011_travel.out","w",stdout);
memset(pre,NULL,sizeof(pre));
n=read();
for(int i=1;i<n;++i){
int x(read()+1),y(read()+1),z(read());
insert(x,y,z),insert(y,x,z);
root=min(root,min(x,y)),realn=max(realn,max(x,y));
}
dfs1(root);
dfs2(root,root);
n=realn;
build(1,n,1);
m=read();
while(m--){
scanf("%s",op);
if(op[0]=='C'){
int x(read()),y(read());
int s(a[x<<1].s),e(a[x<<1].e);
s=dep[s]>dep[e]?s:e;
update(id[s],y,1,n,1);
continue;
}
if(op[0]=='N'){
int x(read()+1),y(read()+1);
change(x,y);
continue;
}
if(op[0]=='S'){
int x(read()+1),y(read()+1);
printf("%d\n",q_sum(x,y));
continue;
}
if(op[1]=='A'){
int x(read()+1),y(read()+1);
printf("%d\n",q_mx(x,y));
continue;
}
int x(read()+1),y(read()+1);
printf("%d\n",q_mn(x,y));
}
return 0;
}
int K(gg());
int main(){;}