CF343D Water Tree

题目翻译（摘自洛谷）

疯狂科学家Mike培养了一颗有根树，由n个节点组成。每个节点是一个要么装满水要么为空的贮水容器. 树的节点用1~n编号，其中根节点为1.对于每个节点的容器，其子节点的容器均在这一容器下方，并且每个节点都由一根可以向下流水的管道与其子节点连接. Mike想要对这棵树做以下操作：
1将节点v注满水. 这样v和其子节点都会充满水.
2将节点v置空. 这样v及其祖先节点（从v到根节点的路径）都会被置空.
3查询当前节点v是否充满水.
初始时，所有节点都为空. Mike已经制定好了他的操作顺序. 在对树进行实验前，他决定先模拟一下操作. 请你帮助Mike得出他操作后的结果.

思路

裸树链剖分，区间修改，单点查询。

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int N=;

 int n,cnt,dcnt,hd[N];

 struct edge

 {

     int to,nxt;

 }v[*N];

 struct node

 {

     int fa,son,sz,dep,tp,s,e;

 }tr[N];

 struct segtree

 {

     int l,r,stat,tag;

 }st[*N];

 void addedge(int x,int y)

 {

     v[++cnt].to=y;

     v[cnt].nxt=hd[x];

     hd[x]=cnt;

 }

 void dfs1(int u)

 {

     tr[u].sz=;

     for(int i=hd[u];i;i=v[i].nxt)

         if(v[i].to!=tr[u].fa)

         {

             tr[v[i].to].fa=u;

             tr[v[i].to].dep=tr[u].dep+;

             dfs1(v[i].to);

             tr[u].sz+=tr[v[i].to].sz;

             if(tr[v[i].to].sz>tr[tr[u].son].sz)

                 tr[u].son=v[i].to;

         }

 }

 void dfs2(int u,int top)

 {

     tr[u].tp=top;

     tr[u].s=++dcnt;

     if(tr[u].son)

     {

         dfs2(tr[u].son,top);

         for(int i=hd[u];i;i=v[i].nxt)

             if(v[i].to!=tr[u].fa&&v[i].to!=tr[u].son)

                 dfs2(v[i].to,v[i].to);

     }

     tr[u].e=dcnt;

 }

 void build(int num,int l,int r)

 {

     st[num].l=l,st[num].r=r;

     st[num].tag=-;

     if(l==r)

         return ;

     int mid=(l+r)/;

     build(*num,l,mid),build(*num+,mid+,r);

 }

 void pushdown(int num)

 {

     if(st[num].tag!=-)

     {

         if(st[num].l!=st[num].r)

         {

             st[*num].stat=st[*num+].stat=st[num].tag;

             st[*num].tag=st[*num+].tag=st[num].tag;

         }

         st[num].tag=-;

     }

 }

 void change(int num,int l,int r,int z)

 {

     if(l>st[num].r||r<st[num].l)

         return ;

     if(st[num].l>=l&&st[num].r<=r)

     {

         st[num].tag=st[num].stat=z;

         return ;

     }

     pushdown(num);

     change(*num,l,r,z),change(*num+,l,r,z);

 }

 int query(int num,int x)

 {

     if(st[num].l>x||st[num].r<x)

         return ;

     if(st[num].l==st[num].r)

         return st[num].stat;

     pushdown(num);

     return query(*num,x)+query(*num+,x);

 }

 void fnd(int x)

 {

     int f1=tr[x].tp;

     while(f1!=)

     {

         change(,tr[f1].s,tr[x].s,);

         x=tr[f1].fa,f1=tr[x].tp;

     }

     change(,,tr[x].s,);

 }

 int main()

 {

     scanf("%d",&n);

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

     {

         int x,y;

         scanf("%d%d",&x,&y);

         addedge(x,y),addedge(y,x);

     }

     dfs1();

     dfs2(,);

     build(,,n);

     int q,x,y;

     scanf("%d",&q);

     while(q--)

     {

         scanf("%d%d",&x,&y);

         switch(x)

         {

             case :

                 change(,tr[y].s,tr[y].e,);

                 break;

             case :

                 fnd(y);

                 break;

             case :

                 printf("%d\n",query(,tr[y].s));

                 break;

         }

     }

     return ;

 }

巴特西

CF343D Water Tree

最新文章

热门文章