LUOGU P2416 泡芙 (缩点+树剖)

解题思路

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

#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;
}

View Code

LUOGU P2416 泡芙 (缩点+树剖)

推荐阅读