POJ 1741 Tree（树分治|ltc男人八题）

﻿﻿

```#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#define eps 1e-6
#define LL long long
#define pii (pair<int, int>)
using namespace std;

const int maxn = 10000 + 100;
const int INF = 0x3f3f3f3f;

int n, root, k, cnt; //root记录重心
int des[maxn], bal[maxn], vis[maxn];//des记录以该节点为祖先的后代数，bal记录以该节点为根的最大子树的节点数
vector<int> G[maxn], L[maxn], dist;

void get_root(int cur, int fa) {
des[cur] = 1;
bal[cur] = 0;
int sz = G[cur].size();
for(int i = 0; i < sz; i++) {
int u = G[cur][i];
if(vis[u] || u == fa) continue;
get_root(u, cur);
des[cur] += des[u];
bal[cur] = max(bal[cur], des[u]);
}
bal[cur] = max(bal[cur], cnt-des[cur]);
if(bal[cur] < bal[root]) root = cur;
}

void dfs(int cur, int init, int fa) {
cnt++;
dist.push_back(init);
int sz = G[cur].size();
for(int i = 0; i < sz; i++) {
int u = G[cur][i];
if(vis[u] || u==fa) continue;
dfs(u, init+L[cur][i], cur);
}
}

int cal(int cur, int init) {
int ans = 0;
dist.clear();
dfs(cur, init, -1);
sort(dist.begin(), dist.end());
int l = 0, r = dist.size()-1;
while(l<r) {
if(dist[l]+dist[r] <= k) ans += r-l, l++;
else r--;
}
return ans;
}

int work(int cur) {
int ans = 0;
vis[cur] = 1;
ans += cal(cur, 0);
for(int i = 0; i < G[cur].size(); i++) {
int u = G[cur][i];
if(vis[u]) continue;
cnt = 0;
ans -= cal(u, L[cur][i]);
root = 0; get_root(u, -1);
ans += work(root);
}
return ans;
}

void init() {
for(int i = 1; i <= n; i++) {
G[i].clear(); L[i].clear();
}
memset(vis, 0, sizeof(vis));
}

int main() {
//	freopen("input.txt", "r", stdin);
while(scanf("%d%d", &n, &k) == 2 && n) {
init();
for(int i = 1; i < n; i++) {
int u, v, l; scanf("%d%d%d", &u, &v, &l);
G[u].push_back(v); L[u].push_back(l);
G[v].push_back(u); L[v].push_back(l);
}
cnt = n; root = 0; bal[0] = INF;
get_root(1, -1);
//cout << root << endl;
int ans = work(root);
printf("%d\n", ans);
}
return 0;
}
```

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

【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