LUOGU P2416 泡芙 (缩点+树剖)

以你之姓@ 2021-09-29 15:32 231阅读 0赞

[传送门][Link 1]

解题思路

首先先缩点，然后将缩完点的权值改成点中路径为1的条数，然后再将边权下放到点权上，求一个每个点到根的路径和，然后用树上2点距离公式算。。刚开始写的线段树，T了2个点。

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

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    
    using namespace std;
    const int MAXN = 300005;
    
    inline int rd(){
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
        while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    
    int n,m,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1],q,xx[MAXN],yy[MAXN],zz[MAXN];
    int dfn[MAXN],low[MAXN],stk[MAXN],top,num,col[MAXN],col_num,Sum[MAXN];
    int head_[MAXN],to_[MAXN<<1],nxt_[MAXN<<1],val_[MAXN<<1],cnt_;
    int fa[MAXN],siz[MAXN],son[MAXN],Top[MAXN],dep[MAXN],w[MAXN];
    bool vis[MAXN];
    
    inline void add(int bg,int ed,int w){
        to[++cnt]=ed,nxt[cnt]=head[bg],val[cnt]=w,head[bg]=cnt;
    }
    
    inline void add_(int bg,int ed,int w){
        to_[++cnt_]=ed,nxt_[cnt_]=head_[bg],head_[bg]=cnt_,val_[cnt_]=w;
    }
    
    void tarjan(int x,int f){
        dfn[x]=low[x]=++num;stk[++top]=x;vis[x]=1;int u;
        for(register int i=head[x];i;i=nxt[i]){
            u=to[i];if(u==f) continue;
            if(!dfn[u]) tarjan(u,x),low[x]=min(low[x],low[u]);
            else if(vis[u]) low[x]=min(low[x],dfn[u]);
        }
        if(low[x]==dfn[x]) {
            col[x]=++col_num;vis[x]=0;
            while(stk[top]!=x) {col[stk[top]]=col_num;vis[stk[top--]]=0;}
            top--;
        }
    }
    
    void dfs1(int x,int f,int d){
        dep[x]=d,fa[x]=f,siz[x]=1;
        int maxson=-1,u;
        for(register int i=head_[x];i;i=nxt_[i]){
            u=to_[i];if(u==f) continue;    
            Sum[u]=Sum[x]+w[u]+val_[i];    
            dfs1(u,x,d+1);siz[x]+=siz[u];
            if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}
        }
    }
    
    void dfs2(int x,int topf){
        Top[x]=topf;
        if(!son[x]) return;dfs2(son[x],topf);int u;
        for(register int i=head_[x];i;i=nxt_[i]){
            u=to_[i];if(u==son[x] || u==fa[x]) continue;
            dfs2(u,u);
        }
    }
    
    int lca(int x,int y){
        while(Top[x]!=Top[y]) {
            if(dep[Top[x]]<dep[Top[y]]) swap(x,y);
            x=fa[Top[x]];
        }   
        return dep[x]>dep[y]?y:x;  
    }
    
    int main(){
        n=rd(),m=rd();int x,y;
        for(register int i=1;i<=m;i++){
            xx[i]=rd(),yy[i]=rd(),zz[i]=rd();
            add(xx[i],yy[i],zz[i]),add(yy[i],xx[i],zz[i]);
        }tarjan(1,0);num=0;
        for(register int i=1;i<=m;i++) {
            if(col[xx[i]]==col[yy[i]]) w[col[xx[i]]]+=zz[i];
            else add_(col[xx[i]],col[yy[i]],zz[i]),add_(col[yy[i]],col[xx[i]],zz[i]);
        }
        Sum[1]=w[1];
        dfs1(1,0,1);dfs2(1,1);q=rd();int Lca;
        while(q--){
            x=rd(),y=rd();Lca=lca(col[x],col[y]);
    //        cout<<Sum[col[x]]<<" "<<Sum[col[y]]<<" "<<Sum[Lca]<<endl;
            puts(((Sum[col[x]]+Sum[col[y]]-2*Sum[Lca]+w[Lca])==0)?"NO":"YES");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/sdfzsyq/p/9733190.html

[Link 1]: https://www.luogu.org/problemnew/show/P2416
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/44fdaac800c34ca3a419a4fe96645ed4.png