题解归档 - cf2231E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2231E
• 本地来源：problems/cf2231E/idea.md
• 题目链接：https://codeforces.com/contest/2231/problem/E
• 原始标题：cf2231E Graph Cutting

思路

cf2231E Graph Cutting

数学记录

• pattern: tree Steiner size / branch counting.
• claim: 三个点生成的最小连通子图边数为 (dist(a,b)+dist(a,c)+dist(b,c))/2，顶点数再加一。
• necessary/sufficient: 若生成子图是路径，则两个端点距离为 d-1，第三点是路径内部点；若不是路径，则存在唯一分叉中心，三个点位于三个不同分支，深度和为 d-1。
• brute/check: 小树枚举所有三元组，用距离公式直接判断。

做法

先 BFS 求全源距离。

路径型：对每对距离为 d-1 的端点，第三点可选路径内部 d-2 个点。

分叉型：枚举中心 root。对每个相邻分支统计深度直方图，在不同分支之间做两层 DP，累加三条深度和为 d-1 的选择。

验证

• python tools/run_exe.py cf2231E 通过官方样例。
• python tools/stress2.py cf2231E -n 1000 --keep-fail 通过。
• n=2000 链与星两种极端树冒烟通过。

代码

来源：problems/cf2231E/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,d;
        scanf("%d%d",&n,&d);
        vector<vector<int> > g(n+1);
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int S=d-1;
        vector<vector<int> > dist(n+1,vector<int>(n+1,-1));
        for(int st=1;st<=n;st++){
            queue<int> q;
            dist[st][st]=0;
            q.push(st);
            while(!q.empty()){
                int u=q.front();
                q.pop();
                for(int v:g[u]){
                    if(dist[st][v]==-1){
                        dist[st][v]=dist[st][u]+1;
                        q.push(v);
                    }
                }
            }
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(dist[i][j]==S) ans+=d-2;
            }
        }
        for(int root=1;root<=n;root++){
            if((int)g[root].size()<3) continue;
            vector<vector<pair<int,ll> > > branches;
            for(int to:g[root]){
                vector<ll> hist(S+1,0);
                function<void(int,int,int)> dfs=[&](int u,int p,int dep){
                    if(dep>S) return;
                    hist[dep]++;
                    for(int v:g[u]){
                        if(v!=p) dfs(v,u,dep+1);
                    }
                };
                dfs(to,root,1);
                vector<pair<int,ll> > cur;
                for(int dep=1;dep<=S;dep++){
                    if(hist[dep]) cur.push_back({dep,hist[dep]});
                }
                if(!cur.empty()) branches.push_back(cur);
            }
            if((int)branches.size()<3) continue;
            sort(branches.begin(),branches.end(),[](const auto &x,const auto &y){
                return x.size()<y.size();
            });
            vector<ll> dp1(S+1,0),dp2(S+1,0);
            vector<int> active1;
            for(int id=0;id<(int)branches.size();id++){
                auto &h=branches[id];
                for(auto [dep,cnt]:h){
                    if(dep<=S) ans+=cnt*dp2[S-dep];
                }
                if(id+1<(int)branches.size()){
                    for(auto [dep,cnt]:h){
                        for(int old:active1){
                            if(dep+old<=S) dp2[dep+old]+=cnt*dp1[old];
                        }
                    }
                }
                for(auto [dep,cnt]:h){
                    if(dp1[dep]==0) active1.push_back(dep);
                    dp1[dep]+=cnt;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}