[模板] POJ-1741 Tree

1741 – 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.

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

8

Source

LouTiancheng@POJ

1.将无根树转换为有根树，从树的重心开始进行点分治（防止退换成一条链，使复杂度变为 $O(n^3)$ ）
2.编写getdeep(int index,int father)函数计算以 $index$ 为根的子树节点到根的距离
3.编写calc(int v,int init)函数用来计算一个以 $v$ 为根节点的( $v$ 的距离初始为init)的排序好了的距离序列，这是可以用 $O(n)$ 的时间求出的。我们定义两个端点 $l,r$ 当 $l k$ 那么 $r–$
4.编写solve()函数进行分治。重复部分就减去calc(v,fa[v]->v.w)

Part 1:全局变量

struct Edge{
int to;
int w;
};

vector  map[MAXN];

bool vis[MAXN]; //标记数组
int son[MAXN]; //子树节点数
int f[MAXN]; //最大子树节点数
int deep[MAXN]; //用于排序的deep
int d[MAXN]; //计算deep的数组


Part 2:获得重心

void getroot(int index,int father){
son[index] = 1; //计录子树大小（现在只有根节点)
f[index] = 0; //初始化最大子树值

for(int i=0;i
   Part 3:获取距离 void getdeep(int index,int father){ deep[++deep[0]] = d[index]; //放入deep数组 deep[0]表示个数 for(int i=0;i   Part 4:计算函数 int calc(int index,int init){ d[index] = init; //初始化index到树根的距离 deep[0] = 0; //初始化个数 getdeep(index,0); //获取深度 sort(deep+1,deep+deep[0]+1); //排序 //如果deep[l] + deep[r] <=k //那么显然所有以l为左端点的点对 和均小于k int l = 1; int r = deep[0]; int sum = 0; while(l   点分治 void solve(int index){ ans += calc(index,0); //计算路径经过根符合条件的点对，此时Index为子树树根，故其距离为0 vis[index] = true; //标记 for(int i=0;i   Part 5:主函数 int main(){ while(scanf("%d%d",&n,&k)==2){ if(!n && !k) break; ans = 0; //初始化答案 root = 0; //初始化重心 memset(vis,0,sizeof(vis)); //初始化标记数组 for(int i=1;i<=n;i++) map[i].clear(); for(int i=0;i 
 
 文章导航 [模板] 树的重心[树状数组] 树状数组及其应用 (adsbygoogle =window.adsbygoogle ||[]).push({});