[HZOI 2016]tree—增强版

解题报告

原题数据水到不行= =

直接找父节点都能上榜= =

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 inline int read(){

     int sum();

     char ch(getchar());

     for(;ch<''||ch>'';ch=getchar());

     for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());

     return sum;

 }

 struct edge{

     int e;

     edge *n;

     edge():e(),n(NULL){}

 }a[],*pre[];

 int tot;

 inline void insert(int s,int e){

     a[++tot].e=e;

     a[tot].n=pre[s];

     pre[s]=&a[tot];

 }

 int n,q;

 char op[];

 bool bj[];

 int fa[];

 inline void dfs(int u){

     for(edge *i=pre[u];i;i=i->n){

         int e(i->e);

         if(e!=fa[u]){

             fa[e]=u;

             dfs(e);

         }

     }

 }

 inline int query(int u){

     while(!bj[u])

         u=fa[u];

     return u;

 }

 inline int gg(){

     freopen("heoi2016_tree.in","r",stdin);

     freopen("heoi2016_tree.out","w",stdout);

     memset(pre,NULL,sizeof(pre));

     n=read(),q=read();

     bj[]=;

     for(int i=;i<n;++i){

         int x(read()),y(read());

         insert(x,y),insert(y,x);

     }

     dfs();

     while(q--){

         scanf("%s",op);

         int x(read());

         if(op[]=='Q')

             printf("%d\n",query(x));

         else

             bj[x]=;

     }

     return ;

 }

 int K(gg());

 int main(){;}

然而加强版数据真的不是闹着玩的= =

首先我们看，它是一个不断往上爬，直到爬到第一个有标记的点或者是根节点时才停止的过程，那么我们很容易想到树剖，从当前节点往上爬就好了

同时我们注意到，题目要求找离当前节点最近的被标记的祖先，所以我们只要去找深度最深的被标记的祖先即可，而由树链剖分中$dfs$序的性质可知，在同一条链上越深的节点，它的时间戳就越大，那么我们显然可以维护一颗最大值的线段树，假如该点被标记，就把它的时间戳加入线段树

剩下的就很好实现了

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cstdlib>

 using namespace std;

 inline int read(){

     int sum=;

     char ch=getchar();

     for(;ch<''||ch>'';ch=getchar());

     for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());

     return sum;

 }

 struct edge{

     int e,n;

 }a[];

 int pre[];

 int tot;

 inline void insert(int s,int e){

     a[++tot].e=e;

     a[tot].n=pre[s];

     pre[s]=tot;

 }

 int dep[],fa[],son[],size[];

 inline void dfs1(int u){

     size[u]=,son[u]=;

     for(int i=pre[u];i!=-;i=a[i].n){

         int e=a[i].e;

         if(e!=fa[u]){

             fa[e]=u;

             dep[e]=dep[u]+;

             dfs1(e);

             size[u]+=size[e];

             if(size[e]>size[son[u]])

                 son[u]=e;

         }

     }

 }

 int cnt;

 int top[],id[],pos[];

 inline void dfs2(int u,int rt){

     top[u]=rt;

     id[u]=++cnt;

     pos[cnt]=u;

     if(son[u])

         dfs2(son[u],rt);

     else

         return;

     for(int i=pre[u];i!=-;i=a[i].n){

         int e=a[i].e;

         if(e!=fa[u]&&e!=son[u])

             dfs2(e,e);

     }

 }

 int mx[];

 inline void pushup(int i){

     mx[i]=max(mx[i<<],mx[i<<|]);

 }

 inline void update(int pos,int l,int r,int i){

     if(l==r){

         mx[i]=pos;

         return;

     }

     int mid=l+r>>;

     if(pos<=mid)

         update(pos,l,mid,i<<);

     else

         update(pos,mid+,r,i<<|);

     pushup(i);

 }

 inline int query(int ll,int rr,int l,int r,int i){

     if(ll<=l&&r<=rr)

         return mx[i];

     int mid=l+r>>,ret=;

     if(ll<=mid)

         ret=max(query(ll,rr,l,mid,i<<),ret);

     if(mid<rr)

         ret=max(query(ll,rr,mid+,r,i<<|),ret);

     return ret;

 }

 int n,q;

 char op[];

 inline int ask(int x){

     int ret();

     while(x){

         int tmp=query(id[top[x]],id[x],,n,);

         if(tmp)

             ret=dep[ret]>dep[pos[tmp]]?ret:pos[tmp];

         x=fa[top[x]];

     }

     return ret;

 }

 int main(){

     int __size__ =  << ;

     char *__p__ = (char*)malloc(__size__) + __size__;

     __asm__("movl %0, %%esp\n" :: "r"(__p__));

     freopen("tree++.in","r",stdin);

     freopen("tree++.out","w",stdout);

     memset(pre,-,sizeof(pre));

     n=read(),q=read();

     for(int i=;i<n;++i){

         int x=read(),y=read();

         insert(x,y);

     }

     dfs1();

     dfs2(,);

     int x;

     update(id[],,n,);

     for(int i=;i<q;++i){

         scanf("%s",op);

         x=read();

         if(op[]=='Q')

             printf("%d\n",ask(x));

         else

             update(id[x],,n,);

     }

     return ;

 }