树上差分-白红宇的个人博客

树上差分

发布日期：2021-05-14 16:51:18 浏览次数：25 分类：精选文章

本文共 1224 字，大约阅读时间需要 4 分钟。

在这里插入图片描述

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #define IL inline#define x first#define y secondtypedef long long ll;using namespace std;const int N=100010,M=400010;int h[N],e[M],ne[M],idx;int fa[N][18],depth[N];int n,m;int d[N];int q[N];int ans;void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++;}void bfs(){ int tt=0,hh=0; memset(depth,0x3f,sizeof depth); depth[0]=0,depth[1]=1; q[tt++]=1; while(hh<=tt) { int t=q[hh++]; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(depth[j]>depth[t]+1) { depth[j]=depth[t]+1; q[tt++]=j; fa[j][0]=t; for(int k=1;k<=17;k++) fa[j][k]=fa[fa[j][k-1]][k-1]; } } }}int lca(int a,int b){ if(depth[a]
            
             =0;k--) { if(depth[fa[a][k]]>=depth[b]) a=fa[a][k]; } if(a==b) return a; for(int k=17;k>=0;k--) if(fa[a][k]!=fa[b][k]) a=fa[a][k],b=fa[b][k]; return fa[a][0];}int dfs(int u,int fa){ int t=d[u]; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa) continue; int tt=dfs(j,u); if(!tt) ans+=m; else if(tt==1) ans++; t+=tt; } return t;}int main(){ cin>>n>>m; memset(h,-1,sizeof h); for(int i=0;i
             
              >a>>b; add(a,b),add(b,a); } bfs(); for(int i=0;i
              
               >a>>b; d[a]++,d[b]++; d[lca(a,b)]-=2; } dfs(1,-1); cout<
               
                <

上一篇：174. 受欢迎的牛

下一篇：差分约束（专题）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章