SRM 630 Div1 Easy, Egalitarianism3

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13284&rd=16061
頂点数 n, 辺数 n-1 の木が与えられる. 各辺には距離が設定されている. k 個の頂点を選び, 頂点間の距離が全て等しくなるようにしたい. k の最大値を求めよ.
頂点数は 1 以上 50 以下, 各辺の距離は 1 以上 1000 以下とする.

解法

条件を満たす頂点集合は次の三通り

• 任意の 1 頂点 (k = 1)
• 任意の 2 頂点 (k = 2)
• スター型 (k > 2)
  ハブ頂点までの距離が等しく, ハブ頂点までの路を共有しない頂点の集合

スター型については, ハブ頂点を決め, 各頂点への距離を dfs で求める.

解答

#include <iostream>
#include <vector>
#include <algorithm>
 
#define loop(n, i) for(int i=0;i<n;i++)
#define from_to(from, to, i) for(int i=from;i<=to;i++)

using namespace std;
using P = pair<int, int>;
const int MAX_D = 60000;

class Egalitarianism3
{
public:
    int D[MAX_D];
    int latest[MAX_D];
    vector<P> G[100];

    int maxCities (int n, vector <int> a, vector <int> b, vector <int> len)
    {
        loop (n-1, i) {
            G[a[i]-1].emplace_back(b[i]-1, len[i]);
            G[b[i]-1].emplace_back(a[i]-1, len[i]);
        }

        int ans = n >= 2 ? 2 : 1;
        loop (n, i) {
            fill(D, D+MAX_D, 0);
            fill(latest, latest+MAX_D, -1);

            for (P& p : G[i]) {
                dfs(p.first, p.second, i, p.first);
            }
            loop (MAX_D, j) ans = max(D[j], ans);
        }
        return ans;
    }

    void dfs (int n, int d, int rev, int orig) {
        if (latest[d] != orig) {
            latest[d] = orig;
            D[d]++;
        }
        for (P& p : G[n]) if (p.first != rev) {
            dfs(p.first, d+p.second, n, orig);
        }
    }
};

備考

任意の 2 頂点のパターンを見逃してる人が多かった.