hdu5967

看到合肥赛区的题目都是泪啊，期末考完了来补几道

公正来说，这道题我考场确实写不出来，因为我的lct模板不够完美……

我在学习lct的时候不知道为什么代码里加边、删边都是用了一个makeroot的操作

这样我的lct就只能维护无根树而不能维护有根树

但事实上，lct是完全可以维护像这道题有向基环外向树一类有根树

那么怎么加边删边呢？

加边x和x的父亲y：只要先access(x) 再把x所属的Auxiliary Tree的Path parent更改y即可（即splay(x)，fa[x]=y）

删除x和x的父亲y：先access(x)，splay(x)，这时断开Auxiliary Tree上根与左子树的连接即可

当然如果涉及到换根的操作，那还是要用makeroot的，这样lct就能维护有根树了

这道题，我们就是维护森林，成环的边不加（根如果有后继先不加），当遇到修改后继的时候再考虑根的后继是否可以加入，查询即找根是否有后继即可

 #include<bits/stdc++.h>

 using namespace std;

 int son[][],a[],fa[];

 int n,m,pre;

 bool rev[],can[];

 bool root(int x)

 {

     return (son[fa[x]][]!=x&&son[fa

 [x]][]!=x);

 }

 void rot(int x,int w)

 {

     int y=fa[x];

     if (!root(y))

     {

         if (son[fa[y]][]==y) son[fa

 [y]][]=x;

         else son[fa[y]][]=x;

     }

     fa[x]=fa[y];

     son[y][w^]=son[x][w];

     if (son[x][w]) fa[son[x][w]]=y;

     son[x][w]=y; fa[y]=x;

 }

 void splay(int x)

 {

     while (!root(x))

     {

         int y=fa[x];

         if (root(y))

         {

             if (son[y][]==x) rot(x,); 

 else rot(x,);

         }

         else {

             if (son[fa[y]][]==y)

             {

                 if (son[y][]==x) rot

 (y,); else rot(x,);

                 rot(x,);

             }

             else {

                 if (son[y][]==x) rot

 (y,); else rot(x,);

                 rot(x,);

             }

         }

     }

 }

 void access(int x)

 {

     int y=;

     while (x)

     {

         splay(x);

         son[x][]=y;

         y=x; x=fa[x];

     }

 }

 int ask(int x)

 {

     access(x);

     splay(x);

     while (son[x][]) x=son[x][];

     return x;

 }

 void link(int x,int y)

 {

     access(x);

     splay(x);

     fa[x]=y;

 }

 void cut(int x)

 {

     access(x);

     splay(x);

     int y=son[x][];

     if (!y) return;

     fa[y]=son[x][]=;

 }

 void change(int x,int y)

 {

     if (y==a[x]) return;

     int rt=ask(x);

     if (can[x]) cut(x);

     if (x!=rt&&a[rt]&&ask(a[rt])!=ask

 (rt))

     {

         link(rt,a[rt]);

         can[rt]=;

     }

     if (!y) can[x]=;

     else {

         if (ask(x)!=ask(y))

         {

             link(x,y);

             can[x]=;

         }

         else can[x]=;

     }

     a[x]=y;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

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

     {

         scanf("%d",&a[i]);

         can[i]=;

         if (a[i])

         {

             if (ask(a[i])!=ask(i))

             {

                 fa[i]=a[i];

                 can[i]=;

             }

             else can[i]=;

         }

     }

     int ch,x,y;

     for (int i=; i<=m; i++)

     {

         scanf("%d",&ch);

         if (ch==)

         {

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

             change(x,y);

         }

         else {

             scanf("%d",&x);

             y=ask(x);

             printf("%d\n",a[y]?-:y);

         }

     }

 }

巴特西

hdu5967

最新文章

热门文章