| 记录编号 |
532430 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[国家集训队2011]旅游 |
最终得分 |
100 |
| 用户昵称 |
 Hale |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.380 s |
| 提交时间 |
2019-05-29 19:53:11 |
内存使用 |
33.50 MiB |
显示代码纯文本
#include<bits/stdc++.h>
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
const int N=2e5+7;
const int INF=0x7f7f7f;
int m,n,root,cnt,idx,tot,ans;
int son[N],fa[N],size[N],v[N],vt[N],a[N],b[N],dep[N],top[N],id[N],head[N];
struct edge
{
int nx,to,dist;
} e[N];
struct node
{
int sum,mx,mn;
} t[N<<2];
void add_edge(int a,int b,int dist)
{
cnt++;e[cnt].nx=head[a];e[cnt].to=b;e[cnt].dist=dist;head[a]=cnt;
cnt++;e[cnt].nx=head[b];e[cnt].to=a;e[cnt].dist=dist;head[b]=cnt;
}
int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void dfs1(int x,int ff,int deep)
{
dep[x]=deep;
fa[x]=ff;
size[x]=1;
for (int i=head[x];i;i=e[i].nx)
{
int y=e[i].to;
if (y==ff) continue;
vt[y]=e[i].dist;
dfs1(y,x,deep+1);
size[x]+=size[y];
if (size[y]>size[son[x]]) son[x]=y;
}
}
void dfs2(int x,int topf)
{
top[x]=topf;
id[x]=++idx;
v[idx]=vt[x];
if (!son[x]) return;
dfs2(son[x],topf);
for (int i=head[x];i;i=e[i].nx)
{
int y=e[i].to;
if (y==son[x]||y==fa[x]) continue;
dfs2(y,y);
}
}
void push_up(int p)
{
t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
t[p].mn=min(t[ls(p)].mn,t[rs(p)].mn);
t[p].mx=max(t[ls(p)].mx,t[rs(p)].mx);
}
void build(int p,int l,int r)
{
if (l==r) {t[p].sum=t[p].mn=t[p].mx=v[l];return;}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void update(int nl,int nr,int l,int r,int p)
{
if (l==r)
{
t[p].sum=-t[p].sum;
t[p].mn=-t[p].mn;
t[p].mx=-t[p].mx;
return;
}
int mid=(l+r)>>1;
if (nl<=mid) update(nl,nr,l,mid,ls(p));
if (nr>mid) update(nl,nr,mid+1,r,rs(p));
push_up(p);
}
int sum(int nl,int nr,int l,int r,int p)
{
if (nl<=l&&r<=nr) return t[p].sum;
int mid=(l+r)>>1,ans=0;
if (nl<=mid) ans+=sum(nl,nr,l,mid,ls(p));
if (nr>mid) ans+=sum(nl,nr,mid+1,r,rs(p));
return ans;
}
void cc(int pos,int l,int r,int p,int val)
{
if (l==r)
{
t[p].sum=val;
t[p].mn=val;
t[p].mx=val;
return;
}
int mid=(l+r)>>1;
if (pos<=mid) cc(pos,l,mid,ls(p),val);
else cc(pos,mid+1,r,rs(p),val);
push_up(p);
}
int qmax(int nl,int nr,int l,int r,int p)
{
if (nl<=l&&r<=nr) return t[p].mx;
int mid=(l+r)>>1,ans=-INF;
if (nl<=mid) ans=max(ans,qmax(nl,nr,l,mid,ls(p)));
if (nr>mid) ans=max(ans,qmax(nl,nr,mid+1,r,rs(p)));
return ans;
}
int qmin(int nl,int nr,int l,int r,int p)
{
if (nl<=l&&r<=nr) return t[p].mn;
int mid=(l+r)>>1,ans=INF;
if (nl<=mid) ans=min(ans,qmin(nl,nr,l,mid,ls(p)));
if (nr>mid) ans=min(ans,qmin(nl,nr,mid+1,r,rs(p)));
return ans;
}
int query_sum(int x,int y)
{
int ans=0;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=sum(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ans+=sum(id[x]+1,id[y],1,n,1);
return ans;
}
int query_min(int x,int y)
{
int ans=INF;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans=min(ans,qmin(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ans=min(ans,qmin(id[x]+1,id[y],1,n,1));
return ans;
}
int query_max(int x,int y)
{
int ans=-INF;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans=max(ans,qmax(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ans=max(ans,qmax(id[x]+1,id[y],1,n,1));
return ans;
}
void fan(int x,int y)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
update(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
update(id[x]+1,id[y],1,n,1);
}
void change(int x,int val)
{
int p=a[x],q=b[x];
if (dep[p]<dep[q]) swap(p,q);
cc(id[p],1,n,1,val);
}
int main()
{
freopen("nt2011_travel.in","r",stdin);
freopen("nt2011_travel.out","w",stdout);
n=read();
for (int i=1;i<n;i++)
{
int x=read()+1,y=read()+1,z=read();
add_edge(x,y,z);
a[i]=x;b[i]=y;
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
m=read();
for (int i=1;i<=m;i++)
{
char s[4];int x,y;
scanf("%s",s);x=read(),y=read();
if (s[0]=='S') printf("%d\n",query_sum(x+1,y+1));
if (s[0]=='C') change(x,y);
if (s[0]=='N') fan(x+1,y+1);
if (s[0]=='M'&&s[1]=='I') printf("%d\n",query_min(x+1,y+1));
if (s[0]=='M'&&s[1]=='A') printf("%d\n",query_max(x+1,y+1));
}
return 0;
}