| 记录编号 |
216989 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[POJ 3237] 树的维护 |
最终得分 |
100 |
| 用户昵称 |
 一個人的雨 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.567 s |
| 提交时间 |
2016-01-01 19:43:00 |
内存使用 |
32.19 MiB |
显示代码纯文本
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=210000+10;
struct seg{
int l,r,delta;
seg *lc,*rc;
int mx,mi;
seg():mx(0),mi(0),delta(0){}
};
seg *root=new seg;
int Belong[maxn],deep[maxn],size[maxn];
struct edge{
int to,next,w,f;
}G[maxn*5];
int n,m,q,tot=0,h[maxn];
int fa[maxn][16],pos[maxn];
int ans,ind=0;
bool vis[maxn];
int X[maxn],Y[maxn],Z[maxn];
char ch;
int read(){
int num=0; ch=getchar();
while (ch<'!') ch=getchar();
while (ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();}
return num;
}
void add(int x,int y,int z){
++tot; G[tot].to=y; G[tot].w=z;
G[tot].next=h[x]; h[x]=tot;
}
void DFS1(int x,int dep){
deep[x]=dep; size[x]=1; vis[x]=1;
for (int i=1;i<=15;++i){
if (deep[x]<(1<<i)) break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for (int i=h[x];i;i=G[i].next){
int v=G[i].to;
if (vis[v]) continue;
fa[v][0]=x;
DFS1(v,dep+1);
size[x]+=size[v];
}
}
void DFS2(int x,int L){
int k=0; ++ind;
pos[x]=ind;
Belong[x]=L;
for (int i=h[x];i;i=G[i].next)
if (deep[x]<deep[G[i].to]&&size[G[i].to]>size[k])
k=G[i].to;
if (!k) return ;
DFS2(k,L);
for (int i=h[x];i;i=G[i].next)
if (deep[x]<deep[G[i].to]&&k!=G[i].to)
DFS2(G[i].to,G[i].to);
}
void build(seg *p,int l,int r){
p->l=l; p->r=r;
if (l+1==r) return;
else if (l+1<r){
int mid=(l+r)>>1;
p->lc=new seg;
p->rc=new seg;
if (l<mid) build(p->lc,l,mid);
if (mid<r) build(p->rc,mid,r);
}
}
void updatemax(seg *p){//以后带标记时都要这么些
if (p->l+1==p->r) return;
if (p->lc) p->mx=p->lc->mx;
else{
if (p->rc) p->mx=p->rc->mx;
return;
}
if (p->rc)
p->mx=max(p->mx,p->rc->mx);
}
void updatemin(seg *p){
if (p->l+1==p->r) return;
if (p->lc) p->mi=p->lc->mi;
else{
if (p->rc) p->mi=p->rc->mi;
return;
}
if (p->rc)
p->mi=min(p->mi,p->rc->mi);
}
void Swap(seg *p){
int t=p->mx; p->mx=-p->mi; p->mi=-t;
}
void push_down(seg *p){//注意标记的写法，更新儿子的值
if (!p->delta) return;
else{
p->delta=0;
if (p->l+1==p->r) return;
if (p->lc) p->lc->delta^=1;
if (p->rc) p->rc->delta^=1;
if (p->lc) Swap(p->lc);
if (p->rc) Swap(p->rc);
}
}
void update(seg *p,int pos,int val){
if (p->l+1==p->r){p->mx=p->mi=val;return ;}
else{
int mid=(p->l+p->r)>>1;
if (p->delta) push_down(p);
if (pos<mid) update(p->lc,pos,val);
if (mid<=pos) update(p->rc,pos,val);
updatemax(p); updatemin(p);
}
}
void Qmax(seg *p,int l,int r){//对于这道题要改就改到底，否则会影响程序正确性
if (l<=p->l&&p->r<=r){
push_down(p);
if (p->l+1==p->r){
ans=max(ans,p->mx);
return;
}
if (p->lc) Qmax(p->lc,l,r);
if (p->rc) Qmax(p->rc,l,r);
updatemax(p); updatemin(p);
ans=max(ans,p->mx);
}else{
push_down(p);
if (p->l+1==p->r) return;
int mid=(p->l+p->r)>>1;
if (l<mid) Qmax(p->lc,l,r);
if (mid<r) Qmax(p->rc,l,r);
updatemax(p); updatemin(p);
}
}
void change(seg *p,int l,int r){
if (l<=p->l&&p->r<=r){
p->delta^=1;
if (p->l+1==p->r){Swap(p);}
return;}
else{
if (p->delta) push_down(p);
int mid=(p->l+p->r)>>1;
if (l<mid) change(p->lc,l,r);
if (mid<r) change(p->rc,l,r);
updatemax(p); updatemin(p);
}
}
int solve(int u,int v){
int sum=-100000000;
bool flag=0;
if (u==9) flag=1;
while (Belong[u]!=Belong[v]){
ans=-100000000;
Qmax(root,pos[Belong[u]],pos[u]+1);
sum=max(sum,ans); u=fa[Belong[u]][0];
}
ans=-100000000; Qmax(root,pos[v]+1,pos[u]+1);//注意这里的pos[v]+1
sum=max(sum,ans); return sum;
}
int LCA(int a,int b){
if (deep[a]<deep[b]) swap(a,b);
int t=deep[a]-deep[b];
for (int i=0;i<=15;++i)
if (t&(1<<i)) a=fa[a][i];
for (int i=15;~i;i--)
if (fa[a][i]!=fa[b][i]){
a=fa[a][i];b=fa[b][i];}
if (a==b) return a;
else return fa[a][0];
}
void Fchange(int u,int v){
while (Belong[u]!=Belong[v]){
change(root,pos[Belong[u]],pos[u]+1);
u=fa[Belong[u]][0];
if (u==0) return;
}
change(root,pos[v]+1,pos[u]+1);
}
int main(){
freopen("maintaintree.in","r",stdin);
freopen("maintaintree.out","w",stdout);
n=read();
for (int i=1;i<n;++i){
int x,y,z;
x=read(); y=read(); z=read();
add(x,y,z); add(y,x,z);
X[i]=x; Y[i]=y; Z[i]=z;
}
DFS1(1,1);
DFS2(1,1);
build(root,1,ind+1);
update(root,pos[1],-100000000);
for (int i=1;i<n;++i){
int u=X[i],v=Y[i],w=Z[i];
if (deep[u]<deep[v]) swap(u,v);
update(root,pos[u],w);
}
char ch[10]; int x,y;
while (scanf("%s",ch)==1){
if (ch[0]=='D') break;
x=read(); y=read();
if (ch[0]=='C'){
int a=X[x],b=Y[x],Aim;
if(deep[a]>deep[b])Aim=a;else Aim=b;
Z[Aim]=y; update(root,pos[Aim],y);
}else if (ch[0]=='N'){
int zx=LCA(x,y);
Fchange(x,zx); Fchange(y,zx);
}else{
int zx=LCA(x,y);
printf("%d\n",max(solve(x,zx),solve(y,zx)));
}
}
//system("pause");
//碉堡啦！
}