【题解】Luogu P1600 天天爱跑步 LCA+树上差分

客官°小女子只卖身不卖艺 2023-08-17 16:49 80阅读 0赞

真·NOIp day1 T2

众所周知noip按难度顺序出题

感谢洛谷题解@[greenlcat][] 提供思路及写法

写+调+写题解 共计一整个晚上2.5个小时对我今天晚自习啥都没干

分步解决这个题

Step 1 :倍增LCA

本身这题码量就不小，还写树剖LCA，我这个菜鸡调不出来的

倍增求LCA好像没什么可写的，基本操作

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 int n,m,cnt,deep[maxn],fa[maxn][25],w[maxn],head[maxn];
     2 struct edge{
     3     int nxt,to;
     4 }e[maxn*2];
     5 inline void add(int from,int to){
     6     e[++cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;
     7 }
     8 void dfs1(int x){
     9     for(int i=1;(1<<i)<=deep[x];i++){
    10         fa[x][i]=fa[fa[x][i-1]][i-1];
    11     }
    12     for(int i=head[x];i;i=e[i].nxt){
    13         int y=e[i].to;
    14         if(y==fa[x][0])continue;
    15         fa[y][0]=x;
    16         deep[y]=deep[x]+1;
    17         dfs1(y);
    18     }
    19 }
    20 int lca(int x,int y){
    21     if(x==y)return x;
    22     if(deep[x]<deep[y])swap(x,y);
    23     int k=log(deep[x]-deep[y])/log(2);
    24     for(int i=k;i>=0;i--){
    25         if(deep[fa[x][i]]>=deep[y]){
    26             x=fa[x][i];
    27         }
    28         if(x==y)return x;
    29     }
    30     k=log(deep[x])/log(2);
    31     for(int i=k;i>=0;i--){
    32         if(fa[x][i]!=fa[y][i]){
    33             x=fa[x][i];y=fa[y][i];
    34         }
    35     }
    36     return fa[x][0];
    37 }
    38 int main(){
    39     n=read();m=read();
    40     for(int i=1;i<n;i++){
    41         int u,v;u=read();v=read();
    42         add(u,v);add(v,u);
    43     }
    44     deep[1]=1;fa[1][0]=1;dfs1(1);
    45     for(int i=1;i<=n;i++){
    46         w[i]=read();
    47     }
    48     return 0;
    49 }

part one

Step 2 :分析转化

发现模拟每个玩家的复杂度爆炸，分着不行就考虑整体处理

改为枚举每个观察员，看哪些节点对观察员有贡献（可被观察到）

而枚举观察员可以转化成dfs整棵树，O(n)可以接受

考虑对于一个观察员x，如果他在一条$s\_i$到$t\_i$的路径上

1.如果x在$s\_i$到LCA上

当$s\_i$满足$deep\[\{s\_i\}\]=w\[x\]+deep\[x\]$时，$s\_i$对x有1的贡献

2.如果x在$t\_i$到LCA上

当$t\_i$满足$dis\[\{s\_i\},\{t\_i\}\]-deep\[\{t\_i\}\]=w\[x\]-deep\[x\]$时，$t\_i$对x有1的贡献

**所以我们发现，能够对x有贡献的$s\_i$或$t\_i$都在以x为根的子树上**

Step 3 :统计贡献

code（注释都在代码里了）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 struct edge{
     2     int nxt,to;
     3 }e1[maxn*2],e2[maxn*2];
     4 inline void add1(int from,int to){
     5     e1[++cnt1].to=to;e1[cnt1].nxt=h1[from];h1[from]=cnt1;
     6 }
     7 inline void add2(int from,int to){
     8     e2[++cnt2].to=to;e2[cnt2].nxt=h2[from];h2[from]=cnt2;
     9 }
    10 int b1[maxn*2],b2[maxn*2],js[maxn],dis[maxn];
    11 int s[maxn],l[maxn],t[maxn],ans[maxn];
    12 void dfs2(int x){
    13     int t1=b1[w[x]+deep[x]],t2=b2[w[x]-deep[x]+maxn];
    14      //递归前先读桶里的数值，t1是上行桶里的值，t2是下行桶的值
    15     for(int i=head[x];i;i=e[i].nxt){ //递归子树
    16         int y=e[i].to;
    17         if(y==fa[x][0])continue;
    18         dfs2(y);
    19     }
    20     b1[deep[x]]+=js[x];
    21     //上行过程中，当前点作为路径起点产生贡献，入桶
    22     for(int i=h1[x];i;i=e1[i].nxt){
    23         //下行过程中，当前点作为路径终点产生贡献，入桶
    24         int y=e1[i].to;
    25         b2[dis[y]-deep[t[y]]+maxn]++;
    26     }
    27     ans[x]+=b1[w[x]+deep[x]]-t1+b2[w[x]-deep[x]+maxn]-t2;
    28     //计算上、下行桶内差值，累加到ans[x]里面
    29     for(int i=h2[x];i;i=e2[i].nxt){
    30         //回溯前清除以此结点为LCA的起点和终点在桶内产生的贡献，它们已经无效了
    31         int y=e2[i].to;
    32         b1[deep[s[y]]]--;
    33         b2[dis[y]-deep[t[y]]+maxn]--;
    34     }
    35 }
    36 int main(){
    37     for(int i=1;i<=m;i++){
    38         s[i]=read();t[i]=read();
    39         int lcaa=lca(s[i],t[i]); //求LCA
    40         dis[i]=deep[s[i]]+deep[t[i]]-2*deep[lcaa];
    41         js[s[i]]++;//统计以s[i]为起点路径的条数
    42         add1(t[i],i);//第i条路径加入到以t[i]为终点的路径集合中
    43         add2(lcaa,i);//把每条路径归到对应的LCA集合中
    44         if(deep[lcaa]+w[lcaa]==deep[s[i]]){
    45             //如果路径起点或终点刚好为LCA且LCA处是可观察到运动员的,答案--
    46             ans[lcaa]--;
    47         }
    48     }
    49     dfs2(1);
    50     for(int i=1;i<=n;i++){
    51         printf("%lld ",ans[i]);
    52     }
    53     return 0;
    54 }

part two

完整高清无注释code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 using namespace std;
      3 namespace gengyf{
      4 #define ll long long
      5 #define int long long
      6 const int maxn=3e5+10;
      7 inline int read(){
      8     int x=0,f=1;
      9     char c=getchar();
     10     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
     11     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
     12     return x*f;
     13 }
     14 int n,m,cnt,deep[maxn],fa[maxn][25],w[maxn],head[maxn];
     15 int h1[maxn],h2[maxn],cnt1,cnt2;
     16 struct edge{
     17     int nxt,to;
     18 }e[maxn*2],e1[maxn*2],e2[maxn*2];
     19 inline void add(int from,int to){
     20     e[++cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;
     21 }
     22 inline void add1(int from,int to){
     23     e1[++cnt1].to=to;e1[cnt1].nxt=h1[from];h1[from]=cnt1;
     24 }
     25 inline void add2(int from,int to){
     26     e2[++cnt2].to=to;e2[cnt2].nxt=h2[from];h2[from]=cnt2;
     27 }
     28 void dfs1(int x){
     29     for(int i=1;(1<<i)<=deep[x];i++){
     30         fa[x][i]=fa[fa[x][i-1]][i-1];
     31     }
     32     for(int i=head[x];i;i=e[i].nxt){
     33         int y=e[i].to;
     34         if(y==fa[x][0])continue;
     35         fa[y][0]=x;
     36         deep[y]=deep[x]+1;
     37         dfs1(y);
     38     }
     39 }
     40 int lca(int x,int y){
     41     if(x==y)return x;
     42     if(deep[x]<deep[y])swap(x,y);
     43     int k=log(deep[x]-deep[y])/log(2);
     44     for(int i=k;i>=0;i--){
     45         if(deep[fa[x][i]]>=deep[y]){
     46             x=fa[x][i];
     47         }
     48         if(x==y)return x;
     49     }
     50     k=log(deep[x])/log(2);
     51     for(int i=k;i>=0;i--){
     52         if(fa[x][i]!=fa[y][i]){
     53             x=fa[x][i];y=fa[y][i];
     54         }
     55     }
     56     return fa[x][0];
     57 }
     58 int b1[maxn*2],b2[maxn*2],js[maxn],dis[maxn];
     59 int s[maxn],l[maxn],t[maxn],ans[maxn];
     60 void dfs2(int x){
     61     int t1=b1[w[x]+deep[x]],t2=b2[w[x]-deep[x]+maxn];
     62     for(int i=head[x];i;i=e[i].nxt){
     63         int y=e[i].to;
     64         if(y==fa[x][0])continue;
     65         dfs2(y);
     66     }
     67     b1[deep[x]]+=js[x];
     68     for(int i=h1[x];i;i=e1[i].nxt){
     69         int y=e1[i].to;
     70         b2[dis[y]-deep[t[y]]+maxn]++;
     71     }
     72     ans[x]+=b1[w[x]+deep[x]]-t1+b2[w[x]-deep[x]+maxn]-t2;
     73     for(int i=h2[x];i;i=e2[i].nxt){
     74         int y=e2[i].to;
     75         b1[deep[s[y]]]--;
     76         b2[dis[y]-deep[t[y]]+maxn]--;
     77     }
     78 }
     79 int main(){
     80     n=read();m=read();
     81     for(int i=1;i<n;i++){
     82         int u,v;u=read();v=read();
     83         add(u,v);add(v,u);
     84     }
     85     deep[1]=1;fa[1][0]=1;dfs1(1);
     86     for(int i=1;i<=n;i++){
     87         w[i]=read();
     88     }
     89     for(int i=1;i<=m;i++){
     90         s[i]=read();t[i]=read();
     91         int lcaa=lca(s[i],t[i]);
     92         dis[i]=deep[s[i]]+deep[t[i]]-2*deep[lcaa];
     93         js[s[i]]++;
     94         add1(t[i],i);add2(lcaa,i);
     95         if(deep[lcaa]+w[lcaa]==deep[s[i]]){
     96             ans[lcaa]--;
     97         }
     98     }
     99     dfs2(1);
    100     for(int i=1;i<=n;i++){
    101         printf("%lld ",ans[i]);
    102     }
    103     return 0;
    104 }
    105 }
    106 signed main(){
    107   gengyf::main();
    108   return 0;
    109 }

完结撒花花

转载于:https://www.cnblogs.com/gengyf/p/11600205.html

[greenlcat]: https://www.luogu.org/space/show?uid=1034
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/244196ec9b844adb8e317d6801350888.png