题解：P16786 [蓝桥杯 2026 国 A] 安全路径

ADay · 2026-06-08 22:10:55 · 题解

dsu on tree 做法。

Solution

设平稳基站权值为 1，其他为 0，则要求的就是全 1 路径的数量。因此可以用 dsu on tree 统计对于每个点以其为 LCA 的路径数量。

预处理每个点 u 向上最远连续为 1 的祖先 up_u，并记录每个点 u 作为 up_v 的次数 cnt_u，那么子树 u 中的某个点 v 能经过 u 组成路径的条件就是 dep_{up_v}\le dep_u。dsu 重儿子 son_u 时记录变量 now=|\{v|dep_{up_v}\le dep_{son_u}\}|，那么对于 u 其重儿子中满足 dep_{up_v}\le dep_u 的点的数量就是 now-cnt_{son_u}。而对于轻儿子，直接暴力统计即可。

时间复杂度 \mathcal O(n\log n)。

Code

#include<bits/stdc++.h>
using namespace std;
namespace io{快读}using namespace io;
const int N=5e5+5;
int n,tot,cnt[N],up[N],dfn[N],L[N],R[N],dep[N],sz[N],son[N];
vector<int>G[N];
bool is[N];
void dfs1(int u,int f){
    sz[u]=1;
    dep[u]=dep[f]+1;
    dfn[++tot]=u;
    L[u]=tot;
    for(int v:G[u])if(v!=f){
        dfs1(v,u);sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])son[u]=v;
    }R[u]=tot;
    is[u]=!(sz[u]&1);
}
void dfs2(int u,int f){
    if(!is[u])up[u]=n+1;
    else if(is[f])up[u]=up[f];
    else up[u]=u;
    cnt[up[u]]++;
    for(int v:G[u])if(v!=f)dfs2(v,u);
}
long long ans,now;
void dsu(int u,int f,bool kp){
    for(int v:G[u])if(v!=f&&v!=son[u])dsu(v,u,0);
    if(son[u])dsu(son[u],u,1);
    now-=cnt[son[u]];
    ans+=now;
    for(int v:G[u])if(v!=f&&v!=son[u]){
        for(int i=L[v];i<=R[v];i++)
            if(dep[up[dfn[i]]]<=dep[u])ans+=now+1;
        for(int i=L[v];i<=R[v];i++)
            if(dep[up[dfn[i]]]<=dep[u])now++;
    }
    if(is[u])now++;
    if(!kp)now=0;
}
int main(){
    read(n);
    for(int i=1,u,v;i<n;i++){
        read(u,v);
        G[u].push_back(v);
        G[v].push_back(u);
    }dfs1(1,0);dfs2(1,0);
    dep[n+1]=N;
    dsu(1,0,1);
    printf("%lld",ans*2ll);
    return 0;
}