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的过程均可以转化为以下问题:
已知A[1],A[2],...A[m],求满足i<j且A[i]+A[j]<=K的数对(i,j)的个数

对于这个问题,我们先将A从小到大排序。
设B[i]表示满足A[i]+A[p]<=K的最大的p(若不存在则为0)。我们的任务便转化为求出A所对应的B数组。那么,若B[i]>i,那么i对答案的贡献为B[i]-i。
显然,随着i的增大,B[i]的值是不会增大的。利用这个性质,我们可以在线性的时间内求出B数组,从而得到答案。

不过我的代码中这个算的还是有点不一样,他是算i的贡献的时候用B[i] - i, 他是从i开始往后数的,我是从他结束的那个店B[i]往前数的,一直数到最前头,所以代码也有所差别,具体细节见代码,代码中有注释。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 22000;
const int inf = 0x3f3f3f3f;
int head[maxn], tot;
struct Edge {
    int to, next, w;
}edge[maxn];
bool vis[maxn];
int dep[maxn];
int siz[maxn];
int le, ri;
int minn;
int n, k;
void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(vis, false, sizeof(vis));
}
void addedge(int u, int v, int w)
{
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int dfs_size(int u, int fa)//dfs找出每个节点对应的子树的大小
{
    siz[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa || vis[v]) continue;
        siz[u] += dfs_size(v, u);
    }
    return siz[u];
}
void dfs_depth(int u, int fa, int d)//每个节点到根节点的距离
{
    dep[ri++] = d;
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa || vis[v])
            continue;
        dfs_depth(v, u, d + edge[i].w);
    }
}
void get_focus(int u, int fa, int totnum, int &root)//找出树的重心
{
    int m = totnum - siz[u];
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa || vis[v])
            continue;
        get_focus(v, u, totnum, root);
        m = max(m, siz[v]);//找出最大子树
    }
    if (m < minn)//最大子树的最小的数值即重心对应的位置
    {
        minn = m; root = u;
    }
}
int calc(int a, int b)//计算一共有多少符合条件的点对
{
    int e = b - 1, ans = 0;
    sort(dep + a, dep + b);
    for (int i = a; i < b; i++)//对i来说,它的贡献是多大,枚举每一个i
    {
        if (dep[i] > k) break;//如果他大于k了,就说明肯定不满足
        while (e >= a && dep[e] + dep[i] > k) e--;//随着i的增大,e肯定是递减的,只要找到i对应的最大的e小于等于k,那么这个i的贡献就是e-a+1,就是e之前的所有的
        ans += e - a + 1;
        if (e > i) ans--;//这里是在算他的贡献的时候,如果e大于i的话,那么加到答案里肯定有个i,所以要减去1
    }
    return ans >> 1;//一对点算了两次,要除以2
}
int solve(int u)
{
    int totnum = dfs_size(u, 0);
    int ans = 0;
    minn = inf;
    int root;
    get_focus(u, 0, totnum, root);//找到以u为根节点子树的重心root
    vis[root] = true;
    for (int i = head[root]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (vis[v]) continue;
        ans += solve(v);//把所有子树的个数加进来
    }
    le = ri = 0;
    for (int i = head[root]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (vis[v]) continue;
        dfs_depth(v, root, edge[i].w);//找出v的子树里面的
        ans -= calc(le, ri);
        le = ri;
    }
    ans += calc(0, ri);//这里计算就是论文里说的式子:总共的-子树当中的
    for (int i = 0; i < ri; i++)
    {
        if (dep[i] <= k) ans++;
        else break;
    }
    vis[root] = false;
    return ans;
}
int main()
{

    while (~scanf("%d%d", &n, &k))
    {
        if (n == 0 && k == 0) break;
        init();
        int u, v, w;
        for (int i = 1; i < n; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        printf("%d\n", solve(1));
    }
    return 0;
} 
时间: 08-30

POJ 1741 Tree(树分治)的相关文章

POJ 1741 Tree 树分治(点分治)

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

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 1744 tree 树分治

Tree Time Limit: 1000MS   Memory Limit: 30000K       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 ve

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(树的点分治,入门题)

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 点分治

题意 给定 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

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(树分治|ltc男人八题)

 题意:求树上距离小于等于K的点对有多少个. 思路:这道题很容易想到树分治,对于当前的根节点来说,任意两个结点之间要么过根结点,要么在一棵子树中. 那么我们dfs一次求出所有点到根结点的距离,然后用o(n)的时间判定有多少节点对符合,(判断方法稍后说) 但是这样有很多在一颗子树中的节点对我们会求重复,我们需要减去在一棵子树中结点对小于等于k的数量,也就是说,我们这一步求的是在不同子树中距离小于等于k的节点对的个数. 接下来说判定方法,将每个点到根结点的距离排序,用两个指针指向队首和队尾,当结

【BZOJ-1468】Tree 树分治

1468: Tree Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 1025  Solved: 534[Submit][Status][Discuss] Description 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K Input N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入 接下来是k Output 一行,有多少对点之间的距离小于等于k Sample Input 7 1 6 13 6