O(n)的dfs+RMQ就行，试试pku上的加强版...

floyd:

#include <iostream>
using namespace std;

const int maxn = 310, INF = 0x3f3f3f3f;
int dis[maxn][maxn];

int main() {
    int n, s;
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i != j)
                dis[i][j] = INF;
            else
                dis[i][j] = 0;
        }
    for (int i = 1; i < n; i++) {
        int from, to, length;
        cin >> from >> to >> length;
        dis[from][to] = dis[to][from] = length;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j && j != k && i != k)
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    int maxlen = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            maxlen = max(maxlen, dis[i][j]);
    int res = INF;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            if (dis[i][j] == maxlen) {
                for (int k = 1; k <= n; k++)
                    if (dis[i][k] + dis[k][j] == dis[i][j])
                        for (int x = 1; x <= n; x++)
                            if (dis[i][x] + dis[x][j] == dis[i][j] && dis[k][x] <= s)
                                res = min(res, max(min(dis[k][i], dis[x][i]), min(dis[j][k], dis[j][x])));
            }
    cout << res << endl;
    return 0;
}

一年后终于AC了。

一年后，迟来的ac...

怎么办啊

此题完全看不懂

为什么我N^3次 全部0MS过？

莫非常数优化的好？

应该可以从中点扩展核以缩短时间

一次AC

这个题啊…………

初次做这种题，好难啊^^

我做了一下午，不过终于是一次AC了……

我的方法：

先读入数据，用邻接表存（数组模拟），

在用dfs求出任意两点间的距离（正常情况下是O(2^n),但谁让他是一棵树呢，现在是O(n)）

再用n^2时间找到直径（用回溯找路径），

在在直径上枚举所有可能的核（这个简单，但我想了很久，下标极容易错），

每次枚举时dfs计算（O(n)）就可以了…………

好爽啊，这个题沉了一年了终于做出来了…………

可以做到O(n)的呢，用队列优化的动态规划，我就这么过了。

预处理貌似比较麻烦。

以下数据4组是该系统的测评数据

17 1

1 2 5

2 3 3

2 4 3

4 5 2

4 6 5

5 17 1

6 7 3

6 11 4

7 8 3

7 9 6

7 10 3

11 12 3

11 13 2

13 14 1

13 15 3

13 16 1

ANS:13

5 46

1 2 5

1 3 15

1 5 6

2 4 28

ANS:15

8 6

1 3 2

2 3 3

3 4 6

4 5 8

4 6 5

4 7 2

7 8 4

ANS:8

16 11

1 4 4

4 8 3

4 5 3

5 9 2

9 10 1

5 6 5

6 11 4

11 12 2

12 13 1

12 2 2

11 14 3

6 7 3

7 15 3

7 16 3

7 3 5

ANS:8

5 1

1 2 5

2 5 5

2 3 5

2 4 5

ANS:5

奶奶的，终于过了

我记得原题里N

第9个超时，- =

看不懂啊！

靠- -

居然没数据..

去年就挂这题上了啊 再做次吧