Codeforces 526G Spiders Evil Plan

由于做的时候看的是中文题面，第一遍写就被卡题意了：还以为每一条都要过x，那么就是一道动态树根选择2y个叶子的奇怪题目

交完0分gg，才发现题目看错了╮(╯▽╰)╭

the node containing the candy is adjacent to at least one rope covered with a web

完全就是两道题啊。。。。。

首先考虑没有x的做法

贪心显然是对的

1.直径一定要取，否则一定可以通过把与直径最接近（以直径一段为根的lca深度最大）的一条路径改为直径来改善答案

2.剩下的一定从大取到小贪心取（在每次取完后更新每个的数据情况下），同理可证明

然后就可以通过“长链剖分”（把重链剖分里的子树大小改为最深的带权深度）解决没有x的问题了

（目测蛮好写的）

然后考虑一定要把x包含进去

然后是不会证但是感觉很对还能A的想法(⊙﹏⊙)b：

1.先把直径和前2(y-1)【因为每条路径都可以跨两条支链，但是选直径还需要一条路径】大的支链拉进答案（形成一棵树）

2.把x加入答案有两种方案：

　　把离x最近的一条边切掉一半和x所在链连成一条边

　　删掉最短的一条边把x所在链加入答案

——上图中黑色和灰色表示考虑x前做出的答案，红色表示考虑x后加上的边，灰色表示考虑x后去掉的边，左右图分别表示了两种考虑的姿势

两种方案去个比较好的，O(∩_∩)O搞定啦！

实现什么的。。。我是这么写的：

先找直径，拉出来存起来，然后把剩下的（应该是一个大森林）每个节点深度算出来（把直径上的点深度看做0）

瞎搞一波即可，没什么数据结构

 #include <bits/stdc++.h>

 using namespace std;

 int n,tot,lend,post,lengthd,m,N,p,q,o,x,y,lord;

 int fir[],nex[],dis[],to[],len[],d[],sum_d[],rank[];

 int fa[],best[],dep[],top[],ans[],sum[];

 void add(int p,int q,int o)

 {

     nex[++N]=fir[p];len[N]=o;to[N]=q;fir[p]=N;

 }

 void Dfs(int now)

 {

     for(int i=fir[now];i;i=nex[i])

     if(!dis[to[i]])

     {

         dis[to[i]]=dis[now]+len[i];

         Dfs(to[i]);

     }

 }

 void dfs(int now)

 {

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

         dis[i]=;

     dis[now]=;

     Dfs(now);

 }

 void build(int now,int fat,int deep)

 {

     fa[now]=fat;best[now]=deep;dep[now]=deep;rank[now]=lord;

     for(int i=fir[now];i;i=nex[i])

     if(to[i]!=fat)

     {

         build(to[i],now,deep+len[i]);

         best[now]=max(best[now],best[to[i]]);

     }

 }

 void pou(int now,int Top)

 {

     bool sad=;top[now]=Top;

     for(int i=fir[now];i;i=nex[i])

     if(to[i]!=fa[now])

         if(sad && best[now]==best[to[i]])

             sad=,pou(to[i],Top);

         else

             pou(to[i],to[i]);

     if(sad)

         ans[++tot]=dep[now]-dep[fa[top[now]]];

 }

 void find_d()

 {

     dfs();int start=,bes=,end=;

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

         if(dis[i]>bes) bes=dis[i],start=i;

     dfs(start);bes=;

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

         if(dis[i]>bes) bes=dis[i],end=i;

     for(d[lend=]=post=end;post!=start;d[++lend]=post,rank[post]=lend)

         for(int i=fir[post];i;i=nex[i])

             if(dis[to[i]]<dis[post])

             {

                 post=to[i];

                 break;

             }

     lengthd=dis[end]-;

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

         sum_d[i]=dis[d[i]]-;

 }

 int main()

 {

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

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

         scanf("%d%d%d",&p,&q,&o),

         add(p,q,o),add(q,p,o);

     find_d();

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

         for(int j=fir[d[i]];j;j=nex[j])

         {

             if(i> && to[j]==d[i-]) continue;

             if(i<lend && to[j]==d[i+]) continue;

             lord=i;

             build(to[j],d[i],len[j]);

             pou(to[j],to[j]);

         }

     sort(ans+,ans+tot+,greater<int>());

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

         sum[i]=sum[i-]+ans[i];

     int lastans=;

     if()

     {

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

             printf("%d ",d[i]);

         puts("");

     }

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

     {

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

         if(x== && y==)

             int e=;

         x=(x+lastans-)%n+;y=(y+lastans-)%n+;

         y=y*-;

         if(y>=tot)

         {

             lastans=sum[tot]+lengthd;

             printf("%d\n",lastans);

         }

         else

         if(!y)

             if(!dep[x])

             {

                 lastans=lengthd;

                 printf("%d\n",lastans);

             }

             else

             {

                 lastans=best[x]+max(sum_d[rank[x]],lengthd-sum_d[rank[x]]);

                 printf("%d\n",lastans);

             }

         else

         if(dep[x] && best[x]-dep[fa[top[x]]]<ans[y])

         {

             lastans=lengthd+sum[y-];

             int enter=x;

             while(dep[enter] && best[enter]-dep[fa[top[enter]]]<ans[y])

                 enter=fa[top[enter]];

             if(dep[enter])

                 lastans+=max(best[x]-dep[enter],best[x]-best[enter]+ans[y]);

             else

             {

                 lastans+=best[x];

                 if(ans[y]>min(sum_d[rank[x]],lengthd-sum_d[rank[x]]))

                     lastans+=ans[y]-min(sum_d[rank[x]],lengthd-sum_d[rank[x]]);

             }

             printf("%d\n",lastans);

         }

         else

         {

             lastans=sum[y]+lengthd;

             printf("%d\n",sum[y]+lengthd);

         }

     }

     return ;

 }

写的又臭又长╮(╯▽╰)╭

巴特西

Codeforces 526G Spiders Evil Plan

最新文章

热门文章