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 vertices is called valid if and only if dist(u,v) not exceed k. 
Write a program that will count how many pairs which are valid for a given tree.

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l. 
The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

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

Sample Output

8

Source

[email protected]

树分治模板题;

分治算法在树的路径问题中的应用

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=1e4+10,M=2e6+10,inf=1e9+10;
const LL INF=1e18+10,mod=1e9+7;

struct is
{
    int v,w,nex;
}edge[N<<1];
int head[N],edg;
void add(int u,int v,int w)
{
    edge[++edg]=(is){v,w,head[u]};head[u]=edg;
}

int son[N],msi[N],d[N];
int vis[N],deep[N];
int n,K,ans,root,sum;
void groot(int u,int fa)
{
    son[u]=1,msi[u]=0;
    for(int i=head[u];i!=-1;i=edge[i].nex)
    {
        int v=edge[i].v;
        if(v==fa||vis[v])continue;
        groot(v,u);
        son[u]+=son[v];
        msi[u]=max(msi[u],son[v]);
    }
    msi[u]=max(msi[u],sum-son[u]);
    if(msi[u]<msi[root])root=u;
}
void gdeep(int x,int fa)
{
    deep[++deep[0]]=d[x];
    for(int i=head[x];i!=-1;i=edge[i].nex)
    {
        int v=edge[i].v;
        int w=edge[i].w;
        if(v==fa||vis[v])continue;
        d[v]=d[x]+w;
        gdeep(v,x);
    }
}

int rootans(int x,int base)
{
    d[x]=base;deep[0]=0;
    gdeep(x,0);
    sort(deep+1,deep+1+deep[0]);
    int ans=0,l=1,r=deep[0];
    while(l<r)
    {
        if(deep[l]+deep[r]<=K)
        {
            ans+=r-l;
            l++;
        }
        else r--;
    }
    return ans;
}
void dfs(int u)
{
    ans+=rootans(u,0);
    vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].nex)
    {
        int v=edge[i].v;
        int w=edge[i].w;
        if(vis[v])continue;
        ans-=rootans(v,w);
        root=0;sum=son[v];
        groot(v,u);
        dfs(root);
    }
}
void init(int n)
{
    memset(head,-1,sizeof(head));
    memset(msi,0,sizeof(msi));
    memset(son,0,sizeof(son));
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    memset(deep,0,sizeof(deep));
    sum=n;root=0;edg=0;
    msi[0]=inf;
    ans=0;
}
int main()
{
    while(~scanf("%d%d",&n,&K))
    {
        if(n==0&&K==0)break;
        init(n);
        for(int i=1;i<n;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        groot(1,0);
        dfs(root);
        printf("%d\n",ans);
    }
    return 0;
}
时间: 07-28

poj 1744 tree 树分治的相关文章

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

【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

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

HDU 4812 D Tree 树分治+逆元+hash新姿势

题意: 给定n个点的树 K 下面n个数是点权 下面n-1行给出树边. 问: 是否存在一条路径使得路径上点权积 % mod  = K 若存在则输出路径的两端. 若存在多条路径则输出字典序最小的一条. 思路: 按树重心分治. 分成路径是否经过树重心. 然后用力码.. has[x] = u; 表示乘积为x 对应的点是u 但这样has就不能用计数器来优化清空. 所以用2个数组: has[x] = cnt; has_id[x] = u; 这样has里存的是乘积为x是否存在.has_id[x] 来记录点.

POJ 3237 Tree (树链剖分 路径剖分 线段树的lazy标记)

题目链接:http://poj.org/problem?id=3237 一棵有边权的树,有3种操作. 树链剖分+线段树lazy标记.lazy为0表示没更新区间或者区间更新了2的倍数次,1表示为更新,每次更新异或1就可以. 熟悉线段树成段更新就很简单了,最初姿势不对一直wa,还是没有彻底理解lazy标记啊. 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace st

poj 3237 Tree 树链剖分+线段树

Description You are given a tree with N nodes. The tree's nodes are numbered 1 through N and its edges are numbered 1 through N ? 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions