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

· · 题解

考虑几种对答案有贡献的点对 (u,v)。

令 \operatorname{d}(u) 表示 u 的深度，s 表示根节点。

  1. \operatorname{d}(u) = \operatorname{d}(v)
  2. u = v
  3. (u = s) \vee (v = s)
  4. 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

#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，或计算时强制转换。