Submission #3430902

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
//#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 2010

template <typename T, typename U>
class Dijkstra {
    private:
        struct Edge {
            T to;   // 有向辺の行先頂点
            U cost;  // 辺の重み
        };
        typedef pair<U, T> P;       // first: 最短距離 second: 頂点 id
    public:
        // コンストラクタ
        // v … 頂点数, inf: …「無限大」とする値
        Dijkstra(T v, U inf) : m_V(v), m_Inf(inf) {
            m_G.assign(m_V, vector<Edge>());
            //m_Dist.assign(m_V, m_Inf);
            m_PrevP.assign(m_V, -1);
        }
        // 有向辺の追加。負のコストは未対応
        void AddDirEdge(T from, T to, U cost) { m_G[from].push_back({to, cost}); }
        // 無向辺の追加。負のコストは未対応
        void AddUndirEdge(T from, T to, U cost) {
            AddDirEdge(from, to, cost);
            AddDirEdge(to, from, cost);
        }
        // 始点 s から各頂点への最短経路の導出 O(E log V)
        void Calc(T s) {
            m_Dist.assign(m_V, m_Inf);
            // 最短距離が短い順で cand を取り出す
            // 頂点 P.second まで P.first のコストで来れたことを情報として入れておく
            priority_queue<P, vector<P>, greater<P> > cand;
            m_Dist[s] = 0;  // 始点のコストは 0
            cand.push(P(0, s));
            while(!cand.empty()) {
                P p = cand.top(); cand.pop();     // cand のトップを取り出す
                T v = p.second;
                // 頂点 v まで最短経路が、 cand から取り出したものより既に小さいなら何もしない
                if(m_Dist[v] < p.first){ continue; }
                // 現在見ている頂点から延びている辺を全て見る
                for(Edge e : m_G[v]) {
                    if(m_Dist[e.to] > m_Dist[v] + e.cost) {
                        // 現在の最短経路より短くなるなら更新
                        m_Dist[e.to] = m_Dist[v] + e.cost;
                        m_PrevP[e.to] = v;
                        cand.push(P(m_Dist[e.to], e.to));
                    }
                }
            }
        }
        // 始点 s から頂点 t への最短距離を返す O(1)
        // 前処理として Calc(s) が必要
        U GetDist(T t) { return m_Dist[t]; }
        // 始点 s から頂点 t までの経路を vector に入れて返す (s と t 含む)
        // O(V') … V' は最短経路の頂点数
        // 前処理として Calc(s) が必要
        vector<T> GetPath(T t) {
            vector<T> path;
            for(; t != -1; t = m_PrevP[t]) { path.push_back(t); }  // t が s になるまで prev_p[t] を辿っていく
            // このままだと t->s の順になっているので逆順にする
            reverse(path.begin(), path.end());
            return path;
        }
    private:
        const T m_V;                // 頂点の数
        const U m_Inf;              // 無限の代わりとして扱う値
        vector< vector<Edge> > m_G; // 頂点 i から延びている辺の vector(隣接リスト)
        vector<U> m_Dist;           // 各頂点への最短コスト。つまり答え
        vector<T> m_PrevP;          // 最短経路の各頂点を保存(経路復元で利用)
};

int N, K;
int A[MAX_N];
int B[MAX_N];
vector<int> graph[MAX_N];   // 頂点 i から伸びている先
int dist[MAX_N][MAX_N] = {};     // 頂点 i-j 間の距離
int child[MAX_N][MAX_N] = {};    // 頂点 i から頂点 j とは逆方向の子の数

// n より下の子全追加 map を作成
void dfs(map<int, int>& m, int n, int prev) {
    m[n] = 1;
    for(auto& next_n : graph[n]) {
        if(next_n == prev) { continue; }
        dfs(m, next_n, n);
    }
}

// 距離が K/2 を超えたら自分以下の子の数を cand に加えて return
void dfs2(int& cand, int border, int root, int n, int prev) {
    if(dist[root][n] > border) {
        cand += child[n][root] + 1;
        return;
    }
    for(auto& next_n : graph[n]) {
        if(next_n == prev) { continue; }
        dfs2(cand, border, root, next_n, n);
    }
}

signed main()
{
    cin >> N >> K;
    Dijkstra<int, int> dk(N, INF);
    REP(i, N-1) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
        dk.AddUndirEdge(A[i], B[i], 1);
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }

    // dist の作成
    REP(i, N) {
        dk.Calc(i);
        REP(j, N) { dist[i][j] = dk.GetDist(j); }
    }

#if 0
    REP(i, N) {
        REP(j, N) {
            DBG("dist[%d][%d]: %d\n", i, j, dist[i][j]);
        }
    }
#endif

    // child の作成
    REP(i, N) {
        vector< map<int, int> > tree;
        REP(j, graph[i].size()) {
            map<int, int> m;
            dfs(m, graph[i][j], i);
            tree.push_back(m);
        }
        REP(j, N) {
            if(i == j) {
                child[i][j] = N - 1;
                continue;
            }
            int id = -1; // 頂点 j がいる tree のインデックス
            REP(k, tree.size()) {
                if(tree[k].count(j) != 0) {
                    id = k;
                    break;
                }
            }
            assert(id >= 0);
            REP(k, tree.size()) {
                if(k == id) { continue; }
                child[i][j] += tree[k].size();
            }
        }
    }

#if 0
    REP(i, N) {
        REP(j, N) {
            DBG("child[%d][%d]: %d\n", i, j, child[i][j]);
        }
    }
#endif

    // ある頂点 i を選ぶ(偶数の場合は 2 つ)
    // そこから K/2 でたどりつけない位置のそれ以降の子をすべて切るとき、合計の最小が答え
    int ans = N-1;
    if(K % 2 == 0) {
        REP(i, N) {
            int cand = 0;
            dfs2(cand, K/2, i, i, -1);
            ans = min(ans, cand);
        }
    } else {
        // 奇数の時は root を 2 つにする
        REP(i, N) {
            for(auto& next_root : graph[i]) {
                int cand = 0;
                dfs2(cand, (K - 1) / 2, i, i, next_root);
                dfs2(cand, (K - 1) / 2, next_root, next_root, i);
                ans = min(ans, cand);
            }
        }

    }
    printf("%d\n", ans);
    return 0;
}

Submission Info

Judge Result