题目传送门

Description

从前有一个死宅, 他非常懒而且懒得动弹, 以至于想走最少的路来完成日常活动。

现在告诉你他活动的 $n$ 个地点以及连接这些地点的 $n-1$ 条道路,保证图联通。

定义一条路径 $u$ 到 $v$ 的厌恶度为 $\sum_{i=1}^{m - 1} k^i$ ,其中 $m$ 为 $u$ 到 $v$ 最短路径上点的个数。

他想选择一个地点居住, 使得这个地点到其他所有地点的路径的厌恶度之和最小。

Solution

设$d_i$表示$k+k^2+k^3+\cdots+k^i$, 那么若点u与点v的路径上有$i$条边, 这条路径的厌恶度就是$d_i$.

30分

假设选择一个位于中点左边的点$u$, 这个点左边有$a$个点, 右边有$b$个点.则共产生的厌恶度为$\sum_{i=1}^ad_i+\sum_{i=1}^bd_i$.

注意到如果选择$u$右边的那个点作为答案, 厌恶度变为$\sum_{i=1}^{a+1}d_i+\sum_{i=1}^{b-1}d_i = \sum_{i=1}^ad_i+\sum_{i=1}^bd_i - d_{b} + d_{a+1}$.发现厌恶度变小了.因此可以推断, 选择更靠右的点(不超过中点)是更优的.同理, 选择右边的点也是如此.因此, 当图为链的形态时, 选择中点是最优的.

50分

$n\le 500, k = 2$, 可以以每个点为树根遍历一遍树, 得到每个点作为根时的厌恶度进行比较.

因为树是随机生成的, 利用随机生成的树期望最高树高为$\sqrt{N}$, 平均树高为$\log_2 N$, $\sqrt{500}<23$, 那么产生的最长路径长度大概在$50$以内\footnote{数据中有两个点最长路径长度达到了63, 但真的是随机数据, 嘻嘻!}, 所以答案是可以用一个128位长整数(C++中的\li\li int128)表示的, 用long long(\li int64)分数会少一点吧.

70分

$k=1$, 因为1的任意次幂都为1, 所以一条路径的厌恶度就是路径上边的个数.

设$f(u)$为$u$到其它所有点的厌恶度总和.容易得到

$$ f(v)=f(u)-\text{Size}_v+n-\text{Size}_v $$

其中$\text{Size}_v$表示$v$这棵子树的大小.

随便选一个点作为树根, 遍历一遍树就得到了树根的答案.然后再遍历一遍树, 得到其它点的答案.

100分

发现难点在于没法对$k ^ 1, k ^ 2, \cdots$直接进行运算.首先$d_i = k+k^2+\cdots + k^i$可以看成是一个公比为$k$首项为$k$的等比级数.类比$2^0+\cdots+2^i=2^i-1$的常识再应用等比数列求和公式.我们可以得到$d_i=\frac{k^{i+1}-k}{k-1}$.

因为分子上的$-k$和分母上的$k-1$是每一项$d$都有的, 本题也无需求出具体的值.因此可以认为$d_i$与$k^{i+1}$相等.

设$p(u,h)$表示树上与$u$距离$h$点的个数.

$d(i,j)$表示$i$的子树中与$i$距离为$j$的点的个数, $u(i,j)$表示不在$u$的子树中与$i$距离为$j$的点的个数.

那么$$d(i,j)=\sum_{v\in \text{son}_i}d(v,j-1)$$

$$u(i,j)=\sum_{i\in \text{son}_f}u(f,j-1)+d(f,j-1)-d(i, j-2)$$

那么点$u$与其它点的总厌恶度就是$\sum_{h=1}p(u,h)k^{h+1}$.

其实可以将$k^i$看成是一个$k$进制数第$i$位上的一个"1".模拟进位, 即$p(u,h)k^{h+1}=(p(u,h) \bmod k) k^{h+1} + \frac{p(u,h)}{k}k^{h+2}$, 当然到最后一位就不用再进位了.

那么这样比较两个$k$进制数的大小最多需要最大路径长度次($\sqrt{N}$).加上前面求$p(u,h)$的复杂度大概是$O(n\sqrt{N})$.总复杂度为$O(n\sqrt{N})$.

Code

/*
 * @Name: 403B.cpp
 * @Author: Lovely_XianShen
 * @Date: 2019-11-07 14:18:48
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int N = 2e4 + 5;

int n, k, tot, head[N];

vector<int>e[N];

int f[N][505], g[N][505];

inline void dfs(int u, int fa) {

    for (int v : e[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
        for (int j = 1; j <= 500; j++)
            f[u][j] += f[v][j - 1];
    }
    f[u][0] = 1;
}

inline void dfs1(int u, int fa) {

    for (int v : e[u]) {
        if (v == fa)
            continue;
        for (int j = 2; j <= 500; j++)
            g[v][j] = f[u][j - 1] + g[u][j - 1] - f[v][j - 2];
        g[v][1] = f[u][0] + g[u][0]; g[v][0] = 1;
        dfs1(v, u);
    }
}

long long ans;

int main() {
    n = read();
    k = read();
    for (int i = 1; i < n; i++) {
        int x = read(), y = read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    dfs1(1, 0);

    for (int i = 1; i <= n; i++)
        for (int j = 500; j >= 1; j--)
            f[i][j] += g[i][j], f[i][j] += f[i][j + 1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 500; j++)
            f[i][j + 1] += f[i][j] / k, f[i][j] %= k;
    ans = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 501; j >= 1; j--) {
            if (f[i][j] < f[ans][j]) {
                ans = i;
                break;
            }
            if (f[ans][j] < f[i][j])
                break;
        }
    printf("%lld\n", ans);
    return 0;
}