2013-11-09 20:06:06Morris
[POJ][樹分治] 1741 - Tree
Description
這題的思路並不難。
考慮一個 rooted tree，決定所有路徑經過 root 的，接下來分別對於子樹再做即可。
現在著重於如何有效的找到樹的重心，否則隨便找到一個點當作 root 演算法可能會退化至 O(n^2)。
樹的重心：重心必須符合其所有子樹的最大值要最小。
如果能有效地查找一個樹的重心，將可以在 O(n logn) 解決這一道問題。
計算所有路徑經過 root 且長度小於等於 k 的個數時，我們需要稍微使用一下排容原理。
備註，我只不過稍微寫慢了一點，就一直死活地停留在 TLE 那裏。
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int to, w;
Edge(int a=0, int b=0):
to(a), w(b) {}
};
int N, K;
vector<Edge> g[10005];
int done[10005];
int mxsubtree[10005], sizesubtree[10005], f[10005];
int visited[10005], vIdx;
int dist[10005], p[10005];
int root;
int dfs(int nd, int p) {
int i, sum = 1, t;
mxsubtree[nd] = 0;
visited[vIdx++] = nd;
for(i = 0; i < g[nd].size(); i++) {
if(g[nd][i].to == p || done[g[nd][i].to])
continue;
t = dfs(g[nd][i].to, nd);
sum += t;
mxsubtree[nd] = max(mxsubtree[nd], t);
}
sizesubtree[nd] = sum;
f[nd] = max(mxsubtree[nd], N-sizesubtree[nd]);
if(f[nd] < f[root]) root = nd;
return sum;
}
void dfs2(int nd, int pp, int d) {
p[vIdx++] = d;
int i;
for(i = 0; i < g[nd].size(); i++) {
if(g[nd][i].to == pp || done[g[nd][i].to])
continue;
dfs2(g[nd][i].to, nd, d+g[nd][i].w);
}
}
int bfsCalc(int root, int init) {// find # of path length <= K which pass root.
int i, j;
vIdx = 0;
dfs2(root, -1, init);
sort(p, p+vIdx);
int pairCnt = 0;
for(i = 0, j = vIdx-1; i < j;) {
if(p[i] + p[j] <= K)
pairCnt += j - i, i++;
else
j--;
}
return pairCnt;
}
int DP(int node) {
int i;
int ret = bfsCalc(node, 0);
done[node] = 1;
for(i = g[node].size()-1; i >= 0; i--) {
if(done[g[node][i].to])
continue;
ret -= bfsCalc(g[node][i].to, g[node][i].w);
N = sizesubtree[g[node][i].to];
root = 0, f[0] = N+1;
dfs(g[node][i].to, -1);
ret += DP(root);
}
return ret;
}
int main() {
/*freopen("in.txt","r+t",stdin);
freopen("out.txt","w+t",stdout);*/
int i, x, y, w;
while(scanf("%d %d", &N, &K) == 2 && N) {
for(i = 1; i <= N; i++)
g[i].clear(), done[i] = 0;
for(i = N-2; i >= 0; i--) {
scanf("%d %d %d", &x, &y, &w);
g[x].push_back(Edge(y, w));
g[y].push_back(Edge(x, w));
}
f[root = 0] = N;
dfs(1, -1);
int ret = DP(root);
printf("%d\n", ret);
}
return 0;
}
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.
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.
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
這題的思路並不難。
考慮一個 rooted tree，決定所有路徑經過 root 的，接下來分別對於子樹再做即可。
現在著重於如何有效的找到樹的重心，否則隨便找到一個點當作 root 演算法可能會退化至 O(n^2)。
樹的重心：重心必須符合其所有子樹的最大值要最小。
如果能有效地查找一個樹的重心，將可以在 O(n logn) 解決這一道問題。
計算所有路徑經過 root 且長度小於等於 k 的個數時，我們需要稍微使用一下排容原理。
備註，我只不過稍微寫慢了一點，就一直死活地停留在 TLE 那裏。
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int to, w;
Edge(int a=0, int b=0):
to(a), w(b) {}
};
int N, K;
vector<Edge> g[10005];
int done[10005];
int mxsubtree[10005], sizesubtree[10005], f[10005];
int visited[10005], vIdx;
int dist[10005], p[10005];
int root;
int dfs(int nd, int p) {
int i, sum = 1, t;
mxsubtree[nd] = 0;
visited[vIdx++] = nd;
for(i = 0; i < g[nd].size(); i++) {
if(g[nd][i].to == p || done[g[nd][i].to])
continue;
t = dfs(g[nd][i].to, nd);
sum += t;
mxsubtree[nd] = max(mxsubtree[nd], t);
}
sizesubtree[nd] = sum;
f[nd] = max(mxsubtree[nd], N-sizesubtree[nd]);
if(f[nd] < f[root]) root = nd;
return sum;
}
void dfs2(int nd, int pp, int d) {
p[vIdx++] = d;
int i;
for(i = 0; i < g[nd].size(); i++) {
if(g[nd][i].to == pp || done[g[nd][i].to])
continue;
dfs2(g[nd][i].to, nd, d+g[nd][i].w);
}
}
int bfsCalc(int root, int init) {// find # of path length <= K which pass root.
int i, j;
vIdx = 0;
dfs2(root, -1, init);
sort(p, p+vIdx);
int pairCnt = 0;
for(i = 0, j = vIdx-1; i < j;) {
if(p[i] + p[j] <= K)
pairCnt += j - i, i++;
else
j--;
}
return pairCnt;
}
int DP(int node) {
int i;
int ret = bfsCalc(node, 0);
done[node] = 1;
for(i = g[node].size()-1; i >= 0; i--) {
if(done[g[node][i].to])
continue;
ret -= bfsCalc(g[node][i].to, g[node][i].w);
N = sizesubtree[g[node][i].to];
root = 0, f[0] = N+1;
dfs(g[node][i].to, -1);
ret += DP(root);
}
return ret;
}
int main() {
/*freopen("in.txt","r+t",stdin);
freopen("out.txt","w+t",stdout);*/
int i, x, y, w;
while(scanf("%d %d", &N, &K) == 2 && N) {
for(i = 1; i <= N; i++)
g[i].clear(), done[i] = 0;
for(i = N-2; i >= 0; i--) {
scanf("%d %d %d", &x, &y, &w);
g[x].push_back(Edge(y, w));
g[y].push_back(Edge(x, w));
}
f[root = 0] = N;
dfs(1, -1);
int ret = DP(root);
printf("%d\n", ret);
}
return 0;
}