[POJ 1741] Tree 点分治

题意

  给定 n 个节点的树.

  求有多少对节点 (u, v) , 满足 dist(u, v) <= K .

  n <= 10000.

实现

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define F(i, a, b) for (register int i = (a); i <= (b); i++)
inline int rd(void) {
    int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -1;
    int x = 0; for (; isdigit(c); c = getchar()) x = x*10+c-‘0‘; return x*f;
}

const int N = 10005;

#define fore(it, x) for (register vector<E>::iterator it = g[x].begin(); it != g[x].end(); it++)
int n, K;
struct E { int v, d; inline E(int _v = 0, int _d = 0): v(_v), d(_d) {} }; vector<E> g[N];
inline void Init(int u, int v, int d) { g[u].push_back(E(v, d)), g[v].push_back(E(u, d)); }

int siz[N], num; bool vis[N];
int s[N], top;
int res;

inline int Siz(int x, int par) {
    siz[x] = 1;
    fore(it, x) if (!vis[it->v] && it->v != par)
        siz[x] += Siz(it->v, x);
    return siz[x];
}
inline int Root(int x, int par) {
    fore(it, x) if (!vis[it->v] && it->v != par) {
        if (siz[it->v] > (num >> 1)) return Root(it->v, x);
    }
    return x;
}

inline void List(int x, int par, int Dist) {
    s[++top] = Dist;
    fore(it, x) if (!vis[it->v] && it->v != par)
        List(it->v, x, Dist + it->d);
}
inline int Calc(int x, int par, int Dist, int sign) {
    top = 0, List(x, par, Dist);
    sort(s+1, s+top+1);
    int sum = 0;
    for (int i = top, j = 0; i >= 1; i--) {
        while (j < i && s[i]+s[j+1] <= K) j++;
        if (i == j) j--;
        sum += j;
    }
    return sum * sign;
}

void Solve(int f) {
    num = Siz(f, -1);
    int x = Root(f, -1);

    res += Calc(x, -1, 0, +1);
    fore(it, x) if (!vis[it->v])
        res += Calc(it->v, x, it->d, -1);

    vis[x] = true;
    fore(it, x) if (!vis[it->v])
        Solve(it->v);
}

int main(void) {
    for (n = rd(), K = rd(); n > 0 || K > 0; n = rd(), K = rd()) {
        F(i, 1, n-1) {
            int u = rd(), v = rd(), d = rd();
            Init(u, v, d);
        }

        memset(vis, 0, sizeof vis), res = 0;
        Solve(1);
        printf("%d\n", res);

        F(i, 1, n) g[i].clear();
    }
    return 0;
}
时间: 08-03

[POJ 1741] Tree 点分治的相关文章

POJ 1741 Tree ——点分治

[题目分析] 这貌似是做过第三道以Tree命名的题目了. 听说树分治的代码都很长,一直吓得不敢写,有生之年终于切掉这题. 点分治模板题目.自己YY了好久才写出来. 然后1A了,开心o(* ̄▽ ̄*)ブ [代码] #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define maxn 20005 #define inf 0x3f3f3f3f using

POJ 1741 Tree 树分治(点分治)

题意:给你一颗带边权树,问你其中 dis(v,u) <= k 的对数 解题思路: 首先推荐大家看 09年国家集训队漆子超 的论文 看到这题  我们可以有三种思路 第一种是枚举起点,遍历整颗树找对数    时间复杂度 为  O(n^2),空间复杂度为 O(n) 第二种是树形dp的思想     每个节点用 长度为 K 数组维护 ,递归求解  时间复杂度为 O(n ^k)空间复杂度 为 O(n) 第三种就是我们要用到的点分治的思想. 这种思想的具体思路是  先找到一个  根  对这个根进行 深搜, 找

POJ 1741 Tree(树分治)

去网上搜题解大多数都是说论文,搜了论文看了看,写的确实挺好,直接复制过来. 不过代码中有些细节还是要注意的,参考这篇http://blog.sina.com.cn/s/blog_6d5aa19a0100o73m.html一段 设X为满足i<j且Depth[i]+Depth[j]<=K的数对(i,j)的个数设Y为满足i<j,Depth[i]+Depth[j]<=K且Belong[i]=Belong[j]数对(i,j)的个数那么我们要统计的量便等于X-Y 求X.Y的过程均可以转化为以下

Poj 1741 Tree (树的分治)

题目链接: Poj 1741 Tree 这个题目Tle的好苦啊,原来一直是树的重心没找对,Tle好长时间,终于对了,好感动,先贴个代码. 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 10010; 8 struct node 9 { 10 int

POJ 1741 Tree(树的点分治,入门题)

Tree Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 21357   Accepted: 7006 Description Give a tree with n vertices,each edge has a length(positive integer less than 1001).Define dist(u,v)=The min distance between node u and v.Give an in

POJ 1741 Tree 树形DP(分治)

链接:id=1741">http://poj.org/problem?id=1741 题意:给出一棵树,节点数为N(N<=10000),给出N-1条边的两点和权值,给出数值k,问树上两点最短距离小于k的点对有多少个. 思路:拿到题的第一反应是LCA问题,只是细一想询问次数极限情况能够达到10000*5000次.即使用Tarjan也是超时没商议的. 2009年国家队论文提供了树的分治思想,对于本题就是树的分治的点分治的应用.每次找到能使含节点最多的子树的节点最少的根分而治之,相同方式分

数据结构(树,点分治):POJ 1741 Tree

Description Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not e

POJ 1741 Tree ——(树分治)

思路参考于:http://blog.csdn.net/yang_7_46/article/details/9966455,不再赘述. 复杂度:找树的重心然后分治复杂度为logn,每次对距离数组dep排序复杂度为nlogn,而找重心的复杂度为dfs的复杂度--O(n),因此总的复杂度为O(nlognlogn). 因为第一次写树分治,留个代码: 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h>

POJ 1741 Tree (树的分治,树的重心)

题意:给一棵树,n个节点,给定一个数k,求任意满足dist(a,b)<=k的点对的数量. 思路: 这道题的思路比较简单,但是细节很多. 此题可以用分治法,如何分治? (1)如果path(a,b)不经过根,那么肯定在根的某棵子树下,递归解决. (2)如果path(a,b)经过根,那么肯定在根的不同子树下,处理它. 怎样处理?如果知道了每棵子树中的节点到根的距离,暂且将每棵子树的节点分到每个独立的桶里.每个节点都可以和其他桶里的点组成点对,只要距离<=k的话就满足要求了.逐个算可能超时了,用个简单