BZOJ4551: [Tjoi2016&Heoi2016]樹

Description

在2016年，佳媛姐姐剛剛學(xué)習(xí)了樹，非常開心?，F(xiàn)在他想解決這樣一個問題：給定一顆有根樹（根為1），有以下兩種操作： 1. 標(biāo)記操作：對某個結(jié)點打上標(biāo)記（在最開始，只有結(jié)點1有標(biāo)記，其他結(jié)點均無標(biāo)記，而且對于某個結(jié)點，可以打多次標(biāo)記。） 2. 詢問操作：詢問某個結(jié)點最近的一個打了標(biāo)記的祖先（這個結(jié)點本身也算自己的祖先） 你能幫幫他嗎?

Input

輸入第一行兩個正整數(shù)N和Q分別表示節(jié)點個數(shù)和操作次數(shù) 接下來N-1行，每行兩個正整數(shù)u,v(1≤u,v≤n)表示u到v有一條有向邊 接下來Q行，形如“opernum”oper為“C”時表示這是一個標(biāo)記操作,oper為“Q”時表示這是一個詢問操作 對于每次詢問操作，1 ≤ N, Q ≤ 100000。

Output

輸出一個正整數(shù)，表示結(jié)果

Sample Input

5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3

Sample Output

1
2
2
1 題解Here! 樹鏈剖分。 打上標(biāo)記就是修改為剖分后的節(jié)點標(biāo)號。 詢問就是求最大值。 附代碼：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA(x) b[x].data
#define LSIDE(x) b[x].l
#define RSIDE(x) b[x].r
#define MAXN 100010
using namespace std;
int n,m,c=1,d=1;
int head[MAXN],deep[MAXN],size[MAXN],son[MAXN],fa[MAXN],top[MAXN],id[MAXN],nid[MAXN];
struct node1{int next,to;
}a[MAXN<<1];
struct node2{int data,l,r;
}b[MAXN<<2];
inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w;
}
inline void add(int x,int y){a[c].to=y;a[c].next=head[x];head[x]=c++;a[c].to=x;a[c].next=head[y];head[y]=c++;
}
void dfs1(int rt){son[rt]=0;size[rt]=1;for(int i=head[rt];i;i=a[i].next){int will=a[i].to;if(!deep[will]){deep[will]=deep[rt]+1;fa[will]=rt;dfs1(will);size[rt]+=size[will];if(size[son[rt]]<size[will])son[rt]=will;}}
}
void dfs2(int rt,int f){nid[d]=rt;id[rt]=d++;top[rt]=f;if(son[rt])dfs2(son[rt],f);for(int i=head[rt];i;i=a[i].next){int will=a[i].to;if(will!=fa[rt]&&will!=son[rt])dfs2(will,will);}
}
inline void pushup(int rt){DATA(rt)=max(DATA(LSON),DATA(RSON));
}
void buildtree(int l,int r,int rt){int mid;LSIDE(rt)=l;RSIDE(rt)=r;if(l==r){DATA(rt)=0;return;}mid=l+r>>1;buildtree(l,mid,LSON);buildtree(mid+1,r,RSON);pushup(rt);
}
void update(int l,int r,int rt){int mid;if(l<=LSIDE(rt)&&RSIDE(rt)<=r){DATA(rt)=l;return;}mid=LSIDE(rt)+RSIDE(rt)>>1;if(l<=mid)update(l,r,LSON);if(mid<r)update(l,r,RSON);pushup(rt);
}
int query(int l,int r,int rt){int mid,ans=0;if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA(rt);mid=LSIDE(rt)+RSIDE(rt)>>1;if(l<=mid)ans=max(ans,query(l,r,LSON));if(mid<r)ans=max(ans,query(l,r,RSON));return ans;
}
void work1(int x,int y){int s=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);s=max(s,query(id[top[x]],id[x],1));x=fa[top[x]];}if(deep[x]>deep[y])swap(x,y);s=max(s,query(id[x],id[y],1));printf("%d\n",nid[s]);return;
}
void work(){char ch[2];int x;while(m--){scanf("%s",ch);x=read();if(ch[0]=='C')update(id[x],id[x],1);if(ch[0]=='Q')work1(1,x);}
}
void init(){int x,y;n=read();m=read();for(int i=1;i<n;i++){x=read();y=read();add(x,y);}deep[1]=1;dfs1(1);dfs2(1,1);buildtree(1,n,1);update(id[1],id[1],1);
}
int main(){init();work();return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/Yangrui-Blog/p/9043403.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ4551: [Tjoi2016Heoi2016]树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。