记录编号 | 438424 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [国家集训队2011]旅游 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | 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(){;}