洛谷P1600 天天爱跑步—

题目传送

　　首先要考虑入手点。先考虑一个一个玩家处理，显然不加优化的话，时间复杂度是O(n)的。发现对于玩家路径上的点都有一个观察员，一个都不能忽视，看起来是很难优化了。在做题时，发现一个思路很难想，就应该考虑一下换个角度思考。OI中如此，生活亦是如此。

　　那就尝试从观察员入手。对于每个玩家，他们在树上的路径一定能分为向上和向下的两段（分的段长度可以为0），设当前玩家x的路径的起点为st，终点为ed，st和ed的LCA为ca，路径长度为dis，当观察员u在玩家x向上走的那一段时，若玩家能在Wu秒时正好被观察员看到，那么一定有dep st-W u=dep u；当观察员u在玩家x从ca向ed走（即向下走）的那一段时，若玩家能在Wu秒时正好被观察员看到，那么一定有dep ed-dep u=dis-W u。因为我们要从观察员入手，所以我们将上面的两个式子中与u有关的移项到左边，无关的移项到右边，就得到了两个式子：1式：dep u+W u=dep st；2式：dep u+ W u=dis-dep ed。其实到这里就有一个显明的思路了：我们枚举每个观察员u，看一下有多少经过u的路径的dep st 等于dep u+W u、有多少经过u的路径的dis-dep ed等于dep u+ W u。这两个“多少”的和去重后（消去同一条路径同时满足两个条件从而计算2次带来的影响）就是观察员u能观察到的玩家数（答案）。为什么呢？其实若该路径的dep st 等于dep u+W u，那么该路径的st肯定不能比u还浅，那u肯定在这个路径向上走的半段；若该路径的dis-dep ed等于dep u+ W u，即dep ed-dep u=dis-W u，若u在该路径向上走的半段，这个式子显然不会成立（dis-Wu就是玩家走到u后再走到ed需要的时间，当u在路径的下半段时，dep ed-dep u正好就是从u走到ed所需的时间，若u在路径的上半段，dep ed-dep u只会比所需时间小），所以u只能在该路径向下走的另半段。　　

　　考虑怎么寻找答案，显然对每个u都暴力一遍所有的路径是不行的了。经过进一步的思考，发现若一条路径经过了u，那么它的起点st和终点ed至少有一个会在u的子树立，若st在u的子树里，那么u就在路径向上的半段；若ed在u的子树里，那么u就在路径向下的半段；特殊地，若st和ed都在u的子树里，那么u同时在路径向上和向下的半段，即u是这条路径的lca，此时应注意上文的去重。而对于一条路径，它可能会对多个u产生答案的贡献，但每次产生贡献时都有一个共同点，就是这条路径的depst 或 dis - dep ed 产生了一次相应的相等。由此可以考虑建2个全局的桶，分别记录dep st等于桶下标值的路径条数和 dis - dep ed 等于下标值的路径条数。但是对于dis - dep ed，发现它可能小于0，为了防止第二个桶的下溢出，第二个桶维护信息的意义应改为dis - dep ed+N 等于下标值的路径条数（N是一个较大的正整数，只要保证dis - dep ed+N恒非负，N可以在空间足够的情况下随便取）。对于每个观察员u，直接去2个桶里相应下标处找答案就行了。

　　但这里有一个问题，即桶里记录的路径条数所包含的路径中，有可能有路径是不经过u的。这好办，可以从根dfs，当dfs到某个路径的起点时入一下第一个桶、终点时入一下第二个桶，等到回溯到这条路径的最高点（即这条路径的ca）时让先前入的桶的相应位置处分别--（出桶）就好了。

　　还有一个问题，即如果只通过上面的操作的话，还是可能会碰到桶里还记录着这条路径，但这条路径仍没经过u，这时只有一种可能，就是这条路径的起点或终点在u的兄弟的子树中，但ca在u的上面。u的答案应该是遍历完以u为根的子树后桶内的相应下标处的增量，即遍历完以u为根的子树后，2个桶会有一些下标处的值发生了变化，这些变化正是以u为根的子树对桶的影响，而只有这些影响量才可能是u的答案，因为这些影响量其实就是在u的子树中的路径起点或终点入桶、ca在u的子树中的路径出桶造成的结果，别忘了只有路径起点或终点在u的子树中，且ca为u或是u的祖先的路径才能对u产生贡献。而这些影响量，就可以通过记录桶的增量来记录。

代码实现：

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #define swap(x,y) (x^=y,y^=x,x^=y)

 using namespace std;

 const int N=,M=;

 int n,m,w[N],son[N],top[N],siz[N],f[N],lst[N];

 int nxt[N<<],to[N<<],cnt,dep[N],dis[M],ans[N];

 int t1[N],t2[N<<],st[N];

 char ch;

 vector<int> lcau[N],lenv[N];

 struct node{

     int num,ord;

 };

 vector<node> lcav[N];

 inline int read()

 {

     int x=;

     ch=getchar();

     while(!isdigit(ch)) ch=getchar();

     while(isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=getchar();

     return x;

 }

 inline void addedge(int u,int v)

 {

     nxt[++cnt]=lst[u];

     lst[u]=cnt;

     to[cnt]=v;

 }

 void dfs1(int u,int fa)//处理f,dep,son,siz    树剖预处理第一遍dfs

 {

     siz[u]=;

     dep[u]=dep[fa]+;

     int t;

     for(int e=lst[u];e;e=nxt[e])

         if((t=to[e])!=fa)

         {

             f[t]=u;

             dfs1(t,u);

             if(siz[t]>siz[son[u]])

                 son[u]=t;

             siz[u]+=siz[t];

         }

 }

 void dfs2(int u,int bos)//处理top    树剖预处理第二遍dfs

 {

     top[u]=bos;

     if(son[u])

     {

         dfs2(son[u],bos);

         int t;

         for(int e=lst[u];e;e=nxt[e])

         {

             if((t=to[e])!=son[u]&&t!=f[u])

                 dfs2(t,t);

         }

     }

 }

 inline int lca(int x,int y)//树剖求LCA过程

 {

     while(top[x]!=top[y])

     {

         if(dep[top[x]]>dep[top[y]])

             x=f[top[x]];

         else

             y=f[top[y]];

     }

     return dep[x]>dep[y]?y:x;

 }

 void dfs(int u)//找答案的dfs

 {

     int aft=t1[dep[u]+w[u]]+t2[w[u]-dep[u]+N];//记录原来桶的量

     for(int e=lst[u];e;e=nxt[e])

     {

         if(to[e]!=f[u])

             dfs(to[e]);

     }

     if(st[u])//入第一个桶

     {

         t1[dep[u]]+=st[u];

     }

     if(lenv[u].size())//入第二个桶

     {

         int l=lenv[u].size(),t;

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

         {

             t=lenv[u][i];

             t2[t-dep[u]+N]++;

         }

     }

     ans[u]=t1[dep[u]+w[u]]+t2[w[u]-dep[u]+N]-aft;//用当前桶的量减原来桶的量得到增量，得当前点u的答案

     if(lcau[u].size())//回溯到u的父亲后以u为ca的路径就没用了，要出桶

     {

         int l=lcau[u].size(),x,y;

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

         {

             x=lcau[u][i];

             y=lcav[u][i].num;

             if(dep[u]+w[u]==dep[x]&&w[u]-dep[u]==dis[lcav[u][i].ord]-dep[y])//去重

                 ans[u]--;

             t1[dep[x]]--;

             t2[dis[lcav[u][i].ord]-dep[y]+N]--;

         }

     }

 }

 int main()

 {

     n=read(),m=read();

     int u,v;

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

     {

         u=read(),v=read();

         addedge(u,v);

         addedge(v,u);

     }

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

         w[i]=read();

     dfs1(,);dfs2(,);

     int ff,l;

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

     {

         u=read(),v=read();

         ff=lca(u,v);//树链剖分求LCA

         st[u]++;//记录以u为路径起点的路径条数

         dis[i]=l=dep[u]+dep[v]-(dep[ff]<<);

         lcau[ff].push_back(u);//记录以ff为ca的路径的起点

         lcav[ff].push_back((node){v,i});//记录以ff为ca的路径的终点和编号

         lenv[v].push_back(l);//记录以v为路径的终点的路径长度

     }

     dfs();

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

     {

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

     }

     return ;

 }

AC注释代码

总结：

　　对于产生全局答案贡献的处理方式：建全局桶。

　　若想从一个存储结构中得到答案，应时刻维护结构以保证其存储的数据的正确性。

　　不写出式子/画出图来，难以更深入地优化或思考。

感觉这道题跟差分的关系不大。只不过修改的复杂度与差分的区间修改都是O(1)，大部分题目的修改复杂度很难有O(1)，故会觉得这道题与差分有点像吧。

巴特西

洛谷P1600 天天爱跑步——题解

最新文章

热门文章