POJ1741(樹分治之點分治)——真男人8題系列

傳送門

題意：給你一顆樹，這棵樹有n個節點，問書中有多少個點對（u,v）他們的距離是小于K的。

題解：樹分治中的點分治。樹分治入門系列。

A：首先從無根樹中随便找一個點為其根節點。然後我們讨論個點。

符合題目要求的點對可以分為兩種

其一為：小于K的點對（u,v）的最小路徑通過根節點root。（顯然點對的最小路徑，LCA（u,v） = root）

其二為：小于K的點對（u,v）的最小路徑不通過通過根節點root。

B： 其二可以由其一通過遞歸得到。是以主要讨論第一種情況

我們用dis[u],dis[v]表示，u,v到根節點的距離。那麼dis[u]+dis[v]<k 的就是所有通過root且小于K的點對數cnt1，但是有些可能不是最小路徑，是以要減去其root子節點rootv對應的有多少通過rootv的點對數cnt2，而子節點可以由遞歸得到，是以ANS加上兩者之差即可:ans+=cnt1-cnt2。

C：每次遞歸的時候，以重心為轉移，根據清華大學ACM國家隊某位大佬的文章證明，根據重心轉移，每一次删除重心遞歸下降劃分子樹，可以将複雜度降低到O(nlognlogn)

D：注意初始化

AC-CDOE

//#include <bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<iostream>
#include <cstring>
using namespace std;
typedef long long ll;
typedef unsigned  long long ull;
const int mx = 4e5 + 7;
const ll inf = 9e12 + 7;
struct node {
    ll w;
    ll to;
};
vector<node> ve[mx];
vector<ll>dis;
ll d[mx], mart[mx];
int vis[mx];
ll n, k, ans = 0, sum, mi;
ll minnode = 0, minnoden = inf;
void find_size(int u, int fa) {
    sum++; //樹大小
    d[u] = 1; //節點本身
    mart[u] = 0;
    int son = ve[u].size(); //msub是節點為u的最大子樹的節點個數
    for (int i = 0; i < son; i++) {
        int v = ve[u][i].to;
        if (vis[v] != 1 && v != fa) {
            find_size(v, u);
            d[u] += d[v];
            mart[u] = max(mart[u], d[v]);
        }
    }
}
void find_point(int u, int fa) {
    int son = ve[u].size();
    for (int i = 0; i < son; i++) {
        int v = ve[u][i].to;
        if (vis[v] != 1&&v != fa) {
            find_point(v, u);
        }
    }
    ll ma=max(mart[u], sum - d[u]);
    if (minnoden > ma) {
        minnode = u;
        minnoden = ma ;
    }
}
void find_dis(int rt, int fa, int d) {
    dis.push_back(d);
    for (int i = 0; i < ve[rt].size(); i++) {
        int v = ve[rt][i].to;
        if (vis[v] == 1||fa == v) continue;
        find_dis(v, rt, d + ve[rt][i].w);
    }
}
ll work(int rt, int d) {
    ll ret = 0;
    dis.clear();
    find_dis(rt, 0, d);
    sort(dis.begin(), dis.end());
    int i = 0, j = dis.size() - 1;
    while (i < j) {
        while (i<j && dis[i] + dis[j]>k) j--;
        ret += j - i;
        i++;
    }
    return ret;
}
void dfs(int rt, int fa) {
    minnode = 0, minnoden = inf;
    sum = 0;
    find_size(rt, fa);
    find_point(rt, fa);
    rt = minnode;
    ans += work(rt, 0);
    vis[rt] = 1;
    for (int i = 0; i < ve[rt].size(); i++) {
        int v = ve[rt][i].to;
        if (rt == v||vis[v]==1) continue;
        ans -= work(v, ve[rt][i].w);
        dfs(v, rt);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//#ifdef ACM_LOCAL
//    freopen("input.txt", "r", stdin);
//	  freopen("output.txt", "w", stdout);
//#endif
    while(cin >> n >> k) {
        if (n == 0 && k == 0)
            break;
        memset(vis, 0, sizeof(vis));
        memset(d, 0, sizeof(d));
        memset(mart, 0, sizeof(mart));
        ans = 0;
        for(int i=1;i<=mx;i++)
            ve[i].clear();
        for (int i = 1; i < n; i++) {
            int u, v, w;
            cin >> u >> v;
            cin >> w;
            node aaa;
            aaa.w = w;
            aaa.to = v;
            ve[u].push_back(aaa);
            aaa.to = u;
            ve[v].push_back(aaa);
        }
        dfs(1, 0);
        cout << ans << endl;
    }
    return 0;
}