| 记录编号 |
327978 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[国家集训队2011]旅游 |
最终得分 |
100 |
| 用户昵称 |
 AntiLeaf |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.231 s |
| 提交时间 |
2016-10-23 16:27:35 |
内存使用 |
11.40 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
struct edge{int to,w,prev;}e[maxn<<1];
void addedge(int,int,int);
void dfs1(int);
void dfs2(int);
void negate(int,int);
void qsum(int,int);
void qmin(int,int);
void qmax(int,int);
void build(int,int,int);
void mset(int,int,int);
void mneg(int,int,int);
void qsum(int,int,int);
void qmin(int,int,int);
void qmax(int,int,int);
void refresh(int);
void pushdown(int);
int sm[maxn<<2],mn[maxn<<2],mx[maxn<<2];
bool lazy[maxn<<2]={false};
int prt[maxn],size[maxn],depth[maxn],son[maxn],top[maxn],dfn[maxn],id[maxn];
int n,m,last[maxn]={0},len=0,w[maxn],low[maxn],tim=0,s,t,d,ans,x,y,z;
char c[15];
int main(){
#define MINE
#ifdef MINE
freopen("nt2011_travel.in","r",stdin);
freopen("nt2011_travel.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
x++;y++;
addedge(x,y,z);
addedge(y,x,z);
}
dfs1(1);
dfs2(1);
build(1,n,1);
scanf("%d",&m);
while(m--){
scanf("%s",c);
if(!strcmp(c,"SUM")){
scanf("%d%d",&x,&y);
x++;y++;
qsum(x,y);
printf("%d\n",ans);
}
else if(!strcmp(c,"MIN")){
scanf("%d%d",&x,&y);
x++;y++;
qmin(x,y);
printf("%d\n",ans);
}
else if(!strcmp(c,"MAX")){
scanf("%d%d",&x,&y);
x++;y++;
qmax(x,y);
printf("%d\n",ans);
}
else if(!strcmp(c,"C")){
scanf("%d%d",&x,&d);
x=dfn[low[x]];
mset(1,n,1);
}
else{
scanf("%d%d",&x,&y);
x++;y++;
negate(x,y);
}
}
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return 0;
}
void addedge(int x,int y,int z){
e[++len].to=y;
e[len].w=z;
e[len].prev=last[x];
last[x]=len;
}
void dfs1(int x){
size[x]=1;
for(int i=last[x];i;i=e[i].prev)if(e[i].to!=prt[x]){
prt[e[i].to]=x;
depth[e[i].to]=depth[x]+1;
w[e[i].to]=e[i].w;
low[(i+1)>>1]=e[i].to;
dfs1(e[i].to);
size[x]+=size[e[i].to];
if(size[e[i].to]>size[son[x]])son[x]=e[i].to;
}
}
void dfs2(int x){
if(x==son[prt[x]])top[x]=top[prt[x]];
else top[x]=x;
dfn[x]=++tim;
id[tim]=x;
if(son[x])dfs2(son[x]);
for(int i=last[x];i;i=e[i].prev)if(e[i].to!=prt[x]&&e[i].to!=son[x])dfs2(e[i].to);
}
void negate(int x,int y){
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
s=dfn[top[x]];
t=dfn[x];
mneg(1,n,1);
x=prt[top[x]];
}
if(depth[x]>depth[y])swap(x,y);
if(x!=y){
s=dfn[x]+1;
t=dfn[y];
mneg(1,n,1);
}
}
void qsum(int x,int y){
ans=0;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
s=dfn[top[x]];
t=dfn[x];
qsum(1,n,1);
x=prt[top[x]];
}
if(depth[x]>depth[y])swap(x,y);
if(x!=y){
s=dfn[x]+1;
t=dfn[y];
qsum(1,n,1);
}
}
void qmin(int x,int y){
ans=~(1<<31);
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
s=dfn[top[x]];
t=dfn[x];
qmin(1,n,1);
x=prt[top[x]];
}
if(depth[x]>depth[y])swap(x,y);
if(x!=y){
s=dfn[x]+1;
t=dfn[y];
qmin(1,n,1);
}
}
void qmax(int x,int y){
ans=1<<31;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
s=dfn[top[x]];
t=dfn[x];
qmax(1,n,1);
x=prt[top[x]];
}
if(depth[x]>depth[y])swap(x,y);
if(x!=y){
s=dfn[x]+1;
t=dfn[y];
qmax(1,n,1);
}
}
void build(int l,int r,int rt){
if(l==r){
sm[rt]=mn[rt]=mx[rt]=w[id[l]];
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
refresh(rt);
}
void mset(int l,int r,int rt){
if(l==r){
sm[rt]=mn[rt]=mx[rt]=d;
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(x<=mid)mset(l,mid,rt<<1);
else mset(mid+1,r,rt<<1|1);
refresh(rt);
}
void mneg(int l,int r,int rt){
if(s<=l&&t>=r){
lazy[rt]^=1;
sm[rt]=-sm[rt];
mn[rt]=-mn[rt];
mx[rt]=-mx[rt];
swap(mn[rt],mx[rt]);
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(s<=mid)mneg(l,mid,rt<<1);
if(t>mid)mneg(mid+1,r,rt<<1|1);
refresh(rt);
}
void qsum(int l,int r,int rt){
if(s<=l&&t>=r){
ans+=sm[rt];
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(s<=mid)qsum(l,mid,rt<<1);
if(t>mid)qsum(mid+1,r,rt<<1|1);
}
void qmin(int l,int r,int rt){
if(s<=l&&t>=r){
ans=min(ans,mn[rt]);
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(s<=mid)qmin(l,mid,rt<<1);
if(t>mid)qmin(mid+1,r,rt<<1|1);
}
void qmax(int l,int r,int rt){
if(s<=l&&t>=r){
ans=max(ans,mx[rt]);
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(s<=mid)qmax(l,mid,rt<<1);
if(t>mid)qmax(mid+1,r,rt<<1|1);
}
void pushdown(int rt){
if(!lazy[rt])return;
int lc=rt<<1,rc=lc|1;
sm[lc]=-sm[lc];
mn[lc]=-mn[lc];
mx[lc]=-mx[lc];
swap(mn[lc],mx[lc]);
lazy[lc]^=1;
sm[rc]=-sm[rc];
mn[rc]=-mn[rc];
mx[rc]=-mx[rc];
swap(mn[rc],mx[rc]);
lazy[rc]^=1;
lazy[rt]=false;
}
void refresh(int rt){
sm[rt]=sm[rt<<1]+sm[rt<<1|1];
mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}