• 最近公共祖先（LCA）

    求法

     

    目录

     1.祖孙询问(倍增)

     2.距离（tarjan+并查集）

    3.次小生成树(kruskal+倍增)

    4. 闇の連鎖（倍增+树形差分）

     1.祖孙询问(倍增)

    因为2^16>4e4,所以开15够了

    信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

    1. #include
    2. using namespace std;
    3. const int N=4e4+10,M=2*N;
    4. int h[N],e[M],ne[M],idx;
    5. int n,m,root;
    6. int depth[N],f[N][16],q[N];//depth存的是每个节点的深度，f存的是以节点i开始跳2的j次方步到达的点
    7. void add(int a,int b)
    8. {
    9.     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    10. }
    11. void bfs()
    12. {
    13.     memset(depth,0x3f,sizeof depth);//初始化每个深度
    14.     int hh=0,tt=0;
    15.     q[0]=root;//把根节点放进队列中
    16.     depth[0]=0,depth[root]=1;//初始化0为虚拟根，因为待会跳的话会跳出根节点，根节点就定义为第一层
    17.     while(hh<=tt)
    18.     {
    19.         int t=q[hh++];
    20.         for(int i=h[t];~i;i=ne[i])
    21.         {
    22.             int j=e[i];
    23.             if(depth[j]>depth[t]+1)//假如这个节点没被更新过
    24.             {
    25.                 depth[j]=depth[t]+1;//更新这个节点的深度
    26.                 q[++tt]=j;//把这个点放进队列中
    27.                 f[j][0]=t;//从j开始跳2^0=1步是t
    28.                 for(int k=1;k<=15;k++)//更新这个点跳的步数走到的点
    29.                     f[j][k]=f[f[j][k-1]][k-1];//用递归的方式更新
    30.             }
    31.         }
    32.     }
    33. }
    34. int lca(int a,int b)
    35. {
    36.     if(depth[a]swap(a,b);//让a是深度最大的点
    37.     //让a跳到跟b同个深度
    38.     for(int i=15;i>=0;i--)//让a跳到跟b同个深度，从大的步数开始跳
    39.         if(depth[f[a][i]]>=depth[b])
    40.             a=f[a][i];//更新跳到的点
    41.     if(a==b) return b;//假如跳到了b，说明b是最近公共祖先
    42.     //在同一深度下一起跳2^i步来找公共祖先
    43.     for(int i=15;i>=0;i--)
    44.       if(f[a][i]!=f[b][i])
    45.       {
    46.           a=f[a][i];//更新跳到的点
    47.           b=f[b][i];//更新跳到的点
    48.       }
    49.       return f[a][0];//因为是跳到公共祖先的下一层，则输出他们点的上一步就是公共祖先了
    50. }
    51. int main()
    52. {
    53.     cin>>n;
    54.     memset(h,-1,sizeof h);
    55.     while(n--)
    56.     {
    57.         int a,b;
    58.         cin>>a>>b;
    59.         if(b==-1) root=a;
    60.         else add(a,b),add(b,a);
    61.     }
    62.     bfs();//先搜索一下深度和跳多少步到那个位置
    63.     cin>>m;
    64.     while(m--)
    65.     {
    66.         int a,b;
    67.         cin>>a>>b;
    68.         int p=lca(a,b);//求一下公共祖先
    69.         if(p==a) puts("1");
    70.         else if(p==b) puts("2");
    71.         else puts("0");
    72.     }
    73.     return 0;
    74. }

     2.距离（tarjan+并查集）

    1171. 距离 - AcWing题库

    tarjan是离线算法就是先把所有询问存下来，然后在求

    1. #include
    2. using namespace std;
    3. typedef pair<int,int> pii;
    4. #define x first
    5. #define y second
    6. const int N=2e5+10,M=2*N;
    7. int n,m;
    8. int h[N],e[M],ne[M],w[M],idx;
    9. int ans[N],dist[N];//ans是记录每个点的答案，diat存的是点跟1号点的距离
    10. int st[N];//st存的是三种状态，0表示还没遍历过，1表示争做遍历，2表示已经遍历过
    11. int p[N];//用来并查集
    12. vector query[N];//第一个存的是询问的点，第二个存的是下标
    13. void add(int a,int b,int c)
    14. {
    15.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    16. }
    17. void dfs(int u,int fa)//处理每个点跟1的距离
    18. {
    19.     for(int i=h[u];~i;i=ne[i])
    20.     {
    21.         int j=e[i];
    22.         if(j==fa) continue;
    23.         dist[j]=dist[u]+w[i];
    24.         dfs(j,u);
    25.     }
    26. }
    27. int find(int x)//并查集
    28. {
    29.     if(p[x]!=x) p[x]=find(p[x]);
    30.     return p[x];
    31. }
    32. void tarjan(int u)
    33. {
    34.     st[u]=1;//标记这个点正在遍历
    35.     for(int i=h[u];~i;i=ne[i])
    36.     {
    37.         int j=e[i];
    38.         if(!st[j])//假如没有遍历过
    39.         {
    40.             tarjan(j);//则遍历一遍这个点
    41.             p[j]=u;//把这个点记录是跟u一个集合的
    42.         }
    43.     }
    44.     for(auto item:query[u])//处理所有询问
    45.     {
    46.         int y=item.x,id=item.y;//y是询问的点，id是询问的位置
    47.         if(st[y]==2)//假如是遍历过的点
    48.         {
    49.             int anc=find(y);//找一下是由那个点的集合，也就是最近公共祖先
    50.             ans[id]=dist[y]+dist[u]-2*dist[anc];//答案就是y与1距离加上u的距离减去最近公共祖先距离的两倍就是答案
    51.         }
    52.     }
    53.     st[u]=2;//标记这个点已经遍历过
    54. }
    55. int main()
    56. {
    57.    scanf("%d%d",&n,&m);
    58.    memset(h,-1,sizeof h);
    59.    for(int i=1;i
    60.    {
    61.        int a,b,c;
    62.        scanf("%d%d%d",&a,&b,&c);
    63.        add(a,b,c),add(b,a,c);
    64.    }
    65.    for(int i=0;i
    66.    {
    67.        int a,b;
    68.        scanf("%d%d",&a,&b);
    69.        if(a!=b)//假如相等则答案就是0，不用求
    70.        {
    71.            query[a].push_back({b,i});//把a询问的b和下标i放进a询问中
    72.            query[b].push_back({a,i});//把b询问的a和下标i放进b询问中
    73.        }
    74.    }
    75.    dfs(1,-1);//处理每个点跟1号点的距离
    76.    for(int i=1;i<=n;i++) p[i]=i;//并查集初始化
    77.    tarjan(1);//做一遍Trajan算法
    78.    for(int i=0;iprintf("%d\n",ans[i]);
    79.     return 0;
    80. }

    3.次小生成树(kruskal+倍增)

    356. 次小生成树 - AcWing题库

    因为2^17>1e5，所以开17就行了

    kruskal求最小生成树，倍增求两点之间的最大和次大边

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e5+10,M=3e5+10,INF=0x3f3f3f3f;
    5. int p[N];//并查集
    6. int h[N],e[M],ne[M],w[M],idx;
    7. int depth[N],d1[N][17],d2[N][17],f[N][17];//depth是深度，d1是某个点走2^j次方步的最大值，d2是次大值，f是某个点走2^k次方步所到达的点
    8. int q[N];
    9. int n,m;
    10. struct Edge
    11. {
    12.     int a,b,w;
    13.     bool used;//用来标记是否是树边
    14.     bool operator <(const Edge &t) const
    15.     {
    16.         return w
    17.     }
    18. }edge[M];
    19. void add(int a,int b,int c)
    20. {
    21.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    22. }
    23. int find(int x)
    24. {
    25.     if(p[x]!=x) p[x]=find(p[x]);
    26.     return p[x];
    27. }
    28. ll kruskal()//求最小生成树
    29. {
    30.     memset(h,-1,sizeof h);//初始化
    31.     for(int i=1;i<=n;i++) p[i]=i;//初始化
    32.     sort(edge,edge+m);//排序
    33.     ll res=0;
    34.     for(int i=0;i
    35.     {
    36.         int a=find(edge[i].a),b=find(edge[i].b),w=edge[i].w;
    37.         if(a!=b)//假如不在一个集合
    38.         {
    39.             p[a]=b;//合并成一个集合
    40.             res+=w;//加上这条最小生成树的边
    41.             edge[i].used=true;//标记一下是树边
    42.             add(edge[i].a,edge[i].b,w),add(edge[i].b,edge[i].a,w);//建树图
    43.         }
    44.     }
    45.     return res;//返回最小生成树的权值和
    46. }
    47. void bfs()//求 深度 最大值 次大值  每个点走几步由那个点更新过来
    48. {
    49.      memset(depth,0x3f,sizeof depth);
    50.      depth[0]=0,depth[1]=1;//0号点是避免跳出去，1号点初始化深度为1
    51.      int hh=0,tt=0;
    52.      q[0]=1;//1号点入队
    53.      while(hh<=tt)
    54.      {
    55.          int t=q[hh++];
    56.          for(int i=h[t];~i;i=ne[i])
    57.          {
    58.              int j=e[i];
    59.              if(depth[j]>depth[t]+1)//假如没有更新过
    60.              {
    61.                  depth[j]=depth[t]+1;//则更新深度
    62.                  q[++tt]=j;//把这个点入队
    63.                  f[j][0]=t;//j这个点走2^0=1步是t
    64.                  d1[j][0]=w[i],d2[j][0]=-INF;//j这个点向上走2^0=1步的最大值是w[i],次大没有标记为负无穷
    65.                  for(int k=1;k<=16;k++)//更新跳到的点
    66.                  {
    67.                      int anc=f[j][k-1];//表示由那个点跳过来的
    68.                      int d[4]={d1[anc][k-1],d2[anc][k-1],d1[j][k-1],d2[j][k-1]};//把j~anc~k的最大次大加到d中
    69.                      f[j][k]=f[anc][k-1];//更新跳的点
    70.                      d1[j][k]=d2[j][k]=-INF;//先初始化为负无穷
    71.                      for(int u=0;u<4;u++)//求一遍最大和次大
    72.                      {
    73.                          int dist=d[u];
    74.                          if(dist>d1[j][k]) d2[j][k]=d1[j][k],d1[j][k]=dist;
    75.                          else if(dist!=d1[j][k]&&dist>d2[j][k]) d2[j][k]=dist;
    76.                      }
    77.                  }
    78.              }
    79.          }
    80.      }
    81. }
    82. int lca(int a,int b,int w)//用来求最大值与次大值能否更新
    83. {
    84.     static int d[2*N];
    85.     int cnt=0;
    86.     if(depth[a]swap(a,b);//假如a深度低，则交换
    87.     for(int k=16;k>=0;k--)//让a与b同个深度
    88.       if(depth[f[a][k]]>=depth[b])//假如还是大，则继续跳
    89.       {
    90.           //把他们跳过的位置的最大值与次大值都记录下来
    91.           d[cnt++]=d1[a][k];
    92.           d[cnt++]=d2[a][k];
    93.           a=f[a][k];//更新跳的点
    94.       }
    95.     if(a!=b)//假如还没跳到一起，也就是没找到最近公共祖宗
    96.     {
    97.        for(int k=16;k>=0;k--)//让a和b一起跳
    98.           if(f[a][k]!=f[b][k])
    99.           {
    100.               //把他们跳过的位置的最大值与次大值都记录下来
    101.               d[cnt++]=d1[a][k];
    102.               d[cnt++]=d2[a][k];
    103.               d[cnt++]=d1[b][k];
    104.               d[cnt++]=d2[b][k];
    105.              a=f[a][k],b=f[b][k];//更新跳过的位置
    106.           }
    107.           //最后也要把跳到最近公共祖先的位置也记录下来
    108.           d[cnt++]=d1[a][0];
    109.           d[cnt++]=d2[a][0];
    110.           d[cnt++]=d1[b][0];
    111.           d[cnt++]=d2[b][0];
    112.     }
    113.     int dist1=-INF,dist2=-INF;
    114.     for(int i=0;i//求一遍最大值和次大值
    115.     {
    116.         int dist=d[i];
    117.         if(dist>dist1) dist2=dist1,dist1=dist;
    118.         else if(dist!=dist1&&dist>dist2) dist2=dist;
    119.     }
    120.     if(w>dist1) return w-dist1;//假如最大值可以用来更新
    121.     if(w>dist2) return w-dist2;//反之次大值可以用来更新
    122.     return INF;//反之为正无穷
    123. }
    124. int main()
    125. {
    126.    scanf("%d%d",&n,&m);
    127.    for(int i=0;i
    128.    {
    129.       int a,b,w;
    130.       scanf("%d%d%d",&a,&b,&w);
    131.       edge[i]={a,b,w};
    132.    }
    133.    ll sum=kruskal();//求一下最小生成树的权值和
    134.    bfs();//求深度 最大值 次大值 更新的点
    135.    ll res=1e18;
    136.    for(int i=0;i
    137.       if(!edge[i].used)//假如是非树边
    138.       {
    139.           int a=edge[i].a,b=edge[i].b,w=edge[i].w;
    140.           res=min(res,sum+lca(a,b,w));//求一遍最大值与次大值能否用来更新
    141.       }
    142.     printf("%lld\n",res);
    143.     return 0;
    144. }

    4. 闇の連鎖（倍增+树形差分）

    352. 闇の連鎖 - AcWing题库

    c表示所有非树边构成的换的树边+1，假如该树边的c大于1 则说明得砍大于1的非树边，则不满足题意方案则+0，假如等于1，说明砍1条非树边就行则方案+1，假如等于0，说明不管怎么砍非树边都满足则+m

    然后这题要用到树形差分就是d[x]+=c,d[y]+=c,d[p]-=c,p是x与y的最近公共祖先

     

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e5+10,M=2e5+10;
    5. int h[N],e[M],ne[M],idx;
    6. int depth[N],f[N][17];//depth是深度，f是记录条几步条到的点
    7. int q[N],d[N];//d存的就是c,就是树形差分
    8. int ans,n,m;;
    9. void add(int a,int b)
    10. {
    11.     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    12. }
    13. void bfs()
    14. {
    15.     memset(depth,0x3f,sizeof depth);
    16.     depth[0]=0,depth[1]=1;//0号点是虚拟原点，1号点让他为跟
    17.     int hh=0,tt=0;
    18.     q[0]=1;//1号点放进队列中
    19.     while(hh<=tt)
    20.     {
    21.         int t=q[hh++];
    22.         for(int i=h[t];~i;i=ne[i])
    23.         {
    24.             int j=e[i];
    25.             if(depth[j]>depth[t]+1)//假如还没更新过
    26.             {
    27.                 depth[j]=depth[t]+1;//则更新
    28.                 q[++tt]=j;//把这个点放进队列中
    29.                 f[j][0]=t;//标记这个点的上一步是t
    30.                 for(int k=1;k<=16;k++)//更新条的其他步到达的点
    31.                     f[j][k]=f[f[j][k-1]][k-1];
    32.             }
    33.         }
    34.     }
    35. }
    36. int lca(int a,int b)
    37. {
    38.     if(depth[a]swap(a,b);//假如a的深度小于b的则交换
    39.     for(int k=16;k>=0;k--)//让a跳到跟b同个深度
    40.         if(depth[f[a][k]]>=depth[b])
    41.            a=f[a][k];//更新跳到的点
    42.     if(a==b) return b;//假如b是最近公共祖先了，则返回
    43.     for(int k=16;k>=0;k--)//让a跟b一起跳
    44.         if(f[a][k]!=f[b][k])
    45.            a=f[a][k],b=f[b][k];//更新两个跳到的位置
    46.     return f[a][0];//返回他们的上一个就是最近公共祖先节点
    47. }
    48. //该点的值就是子树的差分前缀和，跟其他差分一样都是差分前缀和就是该点的值
    49. int dfs(int u,int fa)//返回值是子树差分值前缀和
    50. {
    51.     int res=d[u];//res记录的是树形前缀和，把这个点的差分也加上
    52.     for(int i=h[u];~i;i=ne[i])
    53.     {
    54.         int j=e[i];
    55.         if(j==fa) continue;//避免重复搜索
    56.         int s=dfs(j,u);//s是j这个子树的差分前缀和
    57.         if(s==0) ans+=m;//假如是0则加上m
    58.         else if(s==1) ans++;//假如是1则加1
    59.         res+=s;//把所有子树的差分都加上
    60.     }
    61.     return res;
    62. }
    63. int main()
    64. {
    65.    memset(h,-1,sizeof h);
    66.    scanf("%d%d",&n,&m);
    67.    for(int i=1;i
    68.    {
    69.        int a,b;
    70.        scanf("%d%d",&a,&b);
    71.        add(a,b),add(b,a);
    72.    }
    73.    bfs();//求一遍深度和跳到的点
    74.    for(int i=1;i<=m;i++)
    75.    {
    76.        int a,b;
    77.        scanf("%d%d",&a,&b);
    78.        int p=lca(a,b);//求a跟b的公共祖先
    79.        d[a]++,d[b]++,d[p]-=2;//因为是差分，则a+1，b+1,p-2
    80.    }
    81.    dfs(1,-1);//最后求一遍所有的方案
    82.    printf("%d\n",ans);
    83.     return 0;
    84. }

  • 相关阅读:
    Linux 学习总结（93）—— Linux 管道符使用总结
    Python && JAVA 去除字符串中空格的五种方法
    CISSP学习笔记：事件预防和响应
    three.js中关于摄影机
    【Unity3D】运动模糊特效
    基于resnet网络架构训练图像分类模型
    OKHttp
    跨平台代码编写规范——参考《Loup&卡普》的文档
    OpenCV（二十）：图像卷积
    常见移动端导航类型
  • 原文地址：https://blog.csdn.net/m0_63729880/article/details/126404265