| 记录编号 |
292543 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[POJ 3237] 树的维护 |
最终得分 |
100 |
| 用户昵称 |
 Respawn |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.769 s |
| 提交时间 |
2016-08-09 06:02:42 |
内存使用 |
1.48 MiB |
显示代码纯文本
/*
Name: 有点不一样的树剖
Copyright:
Author: ghostc
Date: 09/08/16 05:55
Description: 将边的权值赋给他的子节点，记录建出的双向边属于哪一个同一条边，然后记录这条边对应的子节点，并赋权值（在
第一次搜索中完成，而取反操作，是区间修改，要有延时标记，并使区间最大值变为区间最小值，所以两个我们都要维护
如以下写到的Nagate和changeall函数就是用于取反操作的
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn=10050;
int id[maxn],v[maxn],son[maxn],top[maxn],size[maxn],ma[maxn*4],mi[maxn*4],deep[maxn],fa[maxn],n,ra[maxn],cnt;
int head[maxn],len,lazy[maxn*4],pos[maxn],bel[maxn*2],Link[maxn*2];
bool flag1[maxn],flag2[maxn];
struct Edge
{
int to,next,dis;
}e[maxn*2];
void Insert(int,int,int);
void Dfs1(int);
void Dfs2(int,int);
void Build(int,int,int);
void change(int,int,int,int,int);
void Negate(int,int);
void changeall(int,int,int,int,int);
int query(int,int);
void Update(int,int,int);
int getsum(int,int,int,int,int);
int main()
{
freopen("maintaintree.in","r",stdin);
freopen("maintaintree.out","w",stdout);
scanf("%d",&n);memset(head,-1,sizeof(head));
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);Insert(x,y,z);Insert(y,x,z);
bel[len]=bel[len-1]=i;
}
fa[1]=1;deep[1]=1;
Dfs1(1);
Dfs2(1,1);
Build(1,1,n);
char ch[10];
while(scanf("%s",ch+1))
{
if(ch[1]=='D')break;
if(ch[1]=='Q')
{
int x,y;scanf("%d%d",&x,&y);
int ans=query(x,y);printf("%d\n",ans);
}
if(ch[1]=='C')
{
int x,y;scanf("%d%d",&x,&y);
change(id[Link[x]],y,1,1,n);
}
if(ch[1]=='N')
{
int x,y;scanf("%d%d",&x,&y);
Negate(x,y);
}
}
}
void Insert(int x,int y,int z)
{
len++;e[len].to=y; e[len].dis=z;
e[len].next=head[x];head[x]=len;
}
void Dfs1(int x)
{
size[x]=1;flag1[x]=1;
for(int i=head[x];i!=-1;i=e[i].next)
{
int j=e[i].to;
if(flag1[j]==1)continue;
deep[j]=deep[x]+1;fa[j]=x;v[j]=e[i].dis;Link[bel[i]]=j;
Dfs1(j);
size[x]+=size[j];
if(size[j]>size[son[x]])son[x]=j;
}
}
void Dfs2(int x,int tp)
{
top[x]=tp;flag2[x]=1;cnt++;id[x]=cnt;pos[cnt]=x;
if(son[x])Dfs2(son[x],tp);
for(int i=head[x];i!=-1;i=e[i].next)
{
int j=e[i].to;
if(flag2[j]==1)continue;
if(j!=fa[x]&&j!=son[x])Dfs2(j,j);
}
}
void Build(int rt,int l,int r)
{
if(l==r)
{
ma[rt]=mi[rt]=v[pos[l]];return;
}
int mid=(l+r)>>1;
Build(lson);
Build(rson);
ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
void Negate(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(deep[fx]<deep[fy])
{
swap(fx,fy);swap(x,y);
}
changeall(id[fx],id[x],1,1,n);
x=fa[fx];fx=top[x];
}
if(deep[x]>deep[y])swap(x,y);
if(id[x]+1<=id[y])changeall(id[x]+1,id[y],1,1,n);
}
void changeall(int s,int t,int rt,int l,int r)
{
if(s<=l&&t>=r)
{
int k=mi[rt];mi[rt]=ma[rt];ma[rt]=k;
mi[rt]=-mi[rt];ma[rt]=-ma[rt];lazy[rt]++;
return;
}
while(lazy[rt])Update(rt,l,r);
int mid=(l+r)>>1;
if(s<=mid)changeall(s,t,lson);
if(t>mid)changeall(s,t,rson);
ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
void change(int s,int c,int rt,int l,int r)
{
if(l==r)
{
ma[rt]=mi[rt]=c;return;
}
while(lazy[rt])Update(rt,l,r);
int mid=(l+r)>>1;
if(s<=mid)change(s,c,lson);
else change(s,c,rson);
ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
int query(int x,int y)
{
int fx=top[x],fy=top[y],ans=-0x7f7f7f7f;
while(fx!=fy)
{
if(deep[fx]<deep[fy])
{
swap(fx,fy);swap(x,y);
}
ans=max(ans,getsum(id[fx],id[x],1,1,n));
x=fa[fx];fx=top[x];
}
if(deep[x]>deep[y])swap(x,y);
if(id[x]+1<=id[y])ans=max(ans,getsum(id[x]+1,id[y],1,1,n));
return ans;
}
int getsum(int s,int t,int rt,int l,int r)
{
if(s<=l&&t>=r)
{
return ma[rt];
}
while(lazy[rt])Update(rt,l,r);
int mid=(l+r)>>1;
if(t<=mid)return getsum(s,t,lson);
if(s>mid)return getsum(s,t,rson);
return max(getsum(s,t,lson),getsum(s,t,rson));
}
void Update(int rt,int l,int r)
{
lazy[rt]--;
int k=ma[rt<<1];ma[rt<<1]=mi[rt<<1];mi[rt<<1]=k;ma[rt<<1]=-ma[rt<<1];mi[rt<<1]=-mi[rt<<1]; lazy[rt<<1]++;
k=ma[rt<<1|1];ma[rt<<1|1]=mi[rt<<1|1];mi[rt<<1|1]=k;ma[rt<<1|1]=-ma[rt<<1|1];mi[rt<<1|1]=-mi[rt<<1|1]; lazy[rt<<1|1]++;
}