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;
}