# 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 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;
{
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];
{
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;
{
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(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);
}
groot(1,0);
dfs(root);
printf("%d\n",ans);
}
return 0;
}```

## 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

## 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