Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Description

Input

Output

Sample Input

5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0

Sample Output

8

---

這題的思路並不難。

考慮一個 rooted tree，決定所有路徑經過 root 的，接下來分別對於子樹再做即可。
現在著重於如何有效的找到樹的重心，否則隨便找到一個點當作 root 演算法可能會退化至 O(n^2)。

樹的重心：重心必須符合其所有子樹的最大值要最小。

如果能有效地查找一個樹的重心，將可以在 O(n logn) 解決這一道問題。

計算所有路徑經過 root 且長度小於等於 k 的個數時，我們需要稍微使用一下排容原理。

備註，我只不過稍微寫慢了一點，就一直死活地停留在 TLE 那裏。

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
    int to, w;
    Edge(int a=0, int b=0):
        to(a), w(b) {}
};
int N, K;
vector<Edge> g[10005];
int done[10005];
int mxsubtree[10005], sizesubtree[10005], f[10005];
int visited[10005], vIdx;
int dist[10005], p[10005];
int root;
int dfs(int nd, int p) {
    int i, sum = 1, t;
    mxsubtree[nd] = 0;
    visited[vIdx++] = nd;
    for(i = 0; i < g[nd].size(); i++) {
        if(g[nd][i].to == p || done[g[nd][i].to])
            continue;
        t = dfs(g[nd][i].to, nd);
        sum += t;
        mxsubtree[nd] = max(mxsubtree[nd], t);
    }
    sizesubtree[nd] = sum;
    f[nd] = max(mxsubtree[nd], N-sizesubtree[nd]);
    if(f[nd] < f[root])    root = nd;
    return sum;
}    
void dfs2(int nd, int pp, int d) {
    p[vIdx++] = d;
    int i;
    for(i = 0; i < g[nd].size(); i++) {
        if(g[nd][i].to == pp || done[g[nd][i].to])
            continue;
        dfs2(g[nd][i].to, nd, d+g[nd][i].w);
    }
}  
int bfsCalc(int root, int init) {// find # of path length <= K which pass root.
    int i, j;
    vIdx = 0;
    dfs2(root, -1, init);
    sort(p, p+vIdx);
    int pairCnt = 0;
    for(i = 0, j = vIdx-1; i < j;) {
        if(p[i] + p[j] <= K)
            pairCnt += j - i, i++;
        else
            j--;
    }
    return pairCnt;
}
int DP(int node) {
    int i;
    int ret = bfsCalc(node, 0);
    done[node] = 1;
    for(i = g[node].size()-1; i >= 0; i--) {
        if(done[g[node][i].to])
            continue;
        ret -= bfsCalc(g[node][i].to, g[node][i].w);
        N = sizesubtree[g[node][i].to];
        root = 0, f[0] = N+1;
        dfs(g[node][i].to, -1);
        ret += DP(root);
    }
    return ret;
}
int main() {
    /*freopen("in.txt","r+t",stdin);
    freopen("out.txt","w+t",stdout);*/
    int i, x, y, w;
    while(scanf("%d %d", &N, &K) == 2 && N) {
        for(i = 1; i <= N; i++)
            g[i].clear(), done[i] = 0;
        for(i = N-2; i >= 0; i--) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(Edge(y, w));
            g[y].push_back(Edge(x, w));
        }
        f[root = 0] = N;
        dfs(1, -1);
        int ret = DP(root);
        printf("%d\n", ret);
    }
    return 0;
}