题解：P11624 [迷宫寻路 Round 3] 挂掉的模板

考虑几种对答案有贡献的点对

(u,v)

。

令

\operatorname{d}(u)

表示

u

的深度，

s

表示根节点。

$\operatorname{d}(u) = \operatorname{d}(v)$
$u = v$
$(u = s) \vee (v = s)$
$LCA(u,v) = s$

令

\operatorname{c}(x)

表示深度为

x

的节点个数，

\operatorname{s}(u)

表示

u

为根节点的子树有多少节点（含根节点），

son_i(1 \le i \le tot)

表示根节点的第

i

个儿子。

分别计算贡献，情况 2，3 显然不再赘述。

对于情况 1，有

2 \times {\sum_{i=1}^{n}\sum_{j=1}^{\operatorname{c}(i)-1}j}

对于情况 4，有

\sum_{i=1}^{tot}\operatorname{s}(son_i)*(n-son_i-1)

对于点对

(u,v)

，若

\operatorname{d}(u) = \operatorname{d}(v)

且

u,v

都在根节点的两个不同子树中，它会被重复计算。

解决方法：情况 1，统计每个

son_i

的答案累加即可，这样操作后情况 1 中的点对都属于同一个子树，情况 4 中的点对都不属于同一个子树。

CODE

CPP

#define MAXN 1000005
int n;
int s;
struct Edge{
    int u,v,nxt;
}e[MAXN];
int head[MAXN],cnt;
inline void addedge(int u,int v){
    ++cnt;
    e[cnt].u=u;
    e[cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
long long ans=0;
int dep[MAXN],num[MAXN];//深度，某一深度上的节点数
long long sz[MAXN];//子树大小
int dfs(int u,int fa){
    dep[u]=dep[fa]+1;++num[dep[u]];
    sz[u]++;
    for (int i = head[u];i;i = e[i].nxt){
        int v=e[i].v;
        sz[u]+=dfs(v,u);
    }
    return sz[u];
}
long long sum[MAXN];
int main(){
    n=read();int fa;
    if (n==1){
        puts("1");
        return 0;
    }
    for (int i = 1;i <= n;i ++){
        fa=read();
        if (fa==i){s=i;continue;}
        addedge(fa,i);
    }
    for (int i = 1;i <= n;i ++) sum[i]=sum[i-1]+i;
    for (int i = head[s]; i ;i = e[i].nxt){//分子树讨论
        int v=e[i].v;
        fill(num+1,num+n+1,0);
        dfs(v,s);
        for (int j = 1;j <= n;j ++) ans+=sum[num[j]-1]*2;//情况1
        ans+=sz[v]*(n-sz[v]-1);情况4
    }
    cout <<ans+n+(n-1)*2;//情况2，3
    return 0;
}

tips：数组也要开 ll，或计算时强制转换。

题解：P11624 [迷宫寻路 Round 3] 挂掉的模板

文章操作

相关推荐

评论

题解：P11624 [迷宫寻路 Round 3] 挂掉的模板