Openjudge原题链接
POJ原题链接
-
题意
输入树的各边及其长度，求路径小于等于k的点对数目 -
题解
目标：寻找长度小于等于k的路径
首先选取一个点作为根节点，那么路径只有两种情况：经过根节点；不经过根节点
如果不经过根节点，那么一定经过最小公共子树的根节点，划归为问题1，可分治求解。 -
假定我们已经有了根节点和树的结构，那么只需要进行一次dfs，在dfs过程中求出每个节点到根节点的距离deep，以及计算出deep[x] + deep[y] <= k的pair数目，然后删除根节点，然后进入每一个子树重新计算新的deep并计算数目。但这样会重复计算。所以在第一次计算时应当减去属于同一棵子树的pair。
-
但是，如果树退化成一条链，那么时间复杂度为O(N ^ 2)。所以需要每次巧妙地选择根节点使得最大的子树最小。即选择重心, 这样保证树的高度不超过O(logN)。
-
更多解释参见代码注释
-
总的时间复杂度为O(N(logN)^2)
-
参考了ACMonster的解释和wwwiskey的解题思路
-
AC代码如下
#if 0
要寻找长度小于等于k的路径
首先选取一个点作为根节点，那么路径只有两种情况：
1.经过根节点
2.不经过根节点
如果不经过根节点，那么一定经过最小公共子树的根节点，划归为问题1，可分治求解。
假定我们已经有了根节点和树的结构，那么只需要进行一次dfs，在dfs过程中求出每个节点到根节点的距离deep，以及
计算出deep[x] + deep[y] <= k的pair数目，然后删除根节点，然后进入每一个子树重新计算新的deep并计算数目。但这
样会重复计算。所以在第一次计算时应当减去属于同一棵子树的pair。
但是，如果树退化成一条链，那么时间复杂度为O(N ^ 2)。所以需要每次巧妙地选择根节点使得最大的子树最小。即选择
重心, 这样保证树的高度不超过O(logN)。
以下是选择重心的源码。
void getroot(int x, int fa)//x表示当前结点，fa表示x的父结点
{
son[x] = 1; F[x] = 0;//F数组记录以x为根的最大子树的大小
for (int i = Link[x]; i; i = e[i].next)
if (e[i].y != fa && !vis[e[i].y])//避免陷入死循环
{
getroot(e[i].y, x);//得到子结点信息
son[x] += son[e[i].y];//计算x结点大小
F[x] = max(F[x], son[e[i].y]);//更新F数组
}
F[x] = max(F[x], sum - son[x]);//sum表示当前树的大小，因为以x为根的情况还要考虑以x的父亲为根的子树大小。
if (F[x]<F[root])root = x;//更新当前根
}
以下是删除根节点后，递归处理每一棵子树（此时还不是子树，是联通块，需要找新的根节点）的源码
int solve(int x)
{
vis[x] = 1;//将当前点标记
for (int i = Link[x]; i; i = e[i].next)
if (!vis[e[i].y])
{
root = 0;//初始化根
sum = e[i].y;//初始化sum
getroot(x, 0);//找连通块的根
solve(e[i].y);//递归处理下一个连通块
}
}
int main()
{
build();//建树
sum = f[0] = n;//初始化sum和f[0]
root = 0;//初始化root
getroot(1, 0);//找根
solve(root);//点分治
}
#endif
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#define MAXN 10005
using namespace std;
struct Edge {
int v, l;//v表示连接到的下一个节点，l表示长度
Edge(int v_, int l_) :v(v_), l(l_) {};
};
vector<Edge> g[MAXN];//用变长数组存储图
vector<int> dep; //用来计算在某图下，以某个节点作为根节点时的各子节点的deep，它不需要知道具体是哪个子节点
int dist[MAXN]; //
int n, k;
int vis[MAXN];
int f[MAXN];//存储在当前图下,以某个节点作为根节点时，得到的最大子树的大小
int root; //当前找到的根节点
int ans; //最后要求的配对数目
int s[MAXN];//s for size，记录在当前图下每个节点的子树大小之和，包括自己
int totalNodes;//n-删除的点的个数
void getroot(int now, int fa) {
int u;
//s的存在是为了累加，然后得出父节点等所有祖先构成子树的大小
s[now] = 1;//自己
f[now] = 0;//存储每个节点的最大子树
for (int i = 0; i < g[now].size(); i++) {//不会陷入死循环的原因之一：树上存在叶节点（只与父节点相连）
u = g[now][i].v;//子节点
if (u != fa && !vis[u]) {//不是父节点且未被切除，如果不排除父节点会陷入死循环
getroot(u, now);//递归地找到子树的最大子树和子树的大小
s[now] += s[u]; //加入子树的大小
f[now] = max(f[now], s[u]);//找最大子树
}
}
f[now] = max(f[now], totalNodes - s[now]);//把父节点等所有祖先当作一棵子树
if (f[now] < f[root]) root = now;//找最大子树最小的根节点
}
void getdep(int now, int fa) {//在某个图某个根节点下求deep，天然的深度是dist[now]
int u;
dep.push_back(dist[now]);
s[now] = 1;
for (int i = 0; i < g[now].size(); i++) {
u = g[now][i].v;
if (u != fa && !vis[u]) {
dist[u] = dist[now] + g[now][i].l;
getdep(u, now);
s[now] += s[u];
}
}
}
int calc(int now, int len) {//在减去属于同一棵子树的时候,len是这个子树到原根节点的距离
//我们把这个距离考虑进来，
dep.clear();
dist[now] = len;//以dist[now]作为基础求deep
getdep(now, 0);//在当前图当前根节点下，计算每个子节点的deep,放入dep数组
sort(dep.begin(), dep.end());
int cnt = 0;//统计数目
int l = 0, r = dep.size() - 1;
/*
用l表示左指针，r表示右指针，i从左向右遍历。
如果dep[i]+dep[j]≤k，则点对(i,t)(i<t≤j)都符合题意，将r-l加入答案中，并且l++；否则r--。
*/
while (l < r) {
if (dep[l] + dep[r] <= k) {
cnt += r - l;
l++;
}
else r--;
}
return cnt;
}
void work(int now) {//以now作为根节点，在当前的图下计算满足题意的pair个数
int u;
ans += calc(now, 0);//以now作为根节点，在当前的图下所有deep[i]+deep[j]<=k的(i,j)的数目
//然后减去属于同一棵子树的(i,j)，于是得到了经过根节点的所有(i,j)路径
vis[now] = true;//剪掉根节点，得到不连通的几棵子树
for (int i = 0; i < g[now].size(); i++) {
u = g[now][i].v;
if (!vis[u]) {
ans -= calc(u, g[now][i].l);//减去属于同一棵子树的(i,j)
f[0] = totalNodes = s[u];//考虑连通的某棵子树，其总的大小
root = 0;
getroot(u, 0);//找到新的根节点
work(root);//递归地增加不经过当前根节点，但是经过新的根节点的路径数目
}
}
}
int main() {
while (cin >> n >> k) {
if (!n && !k) break;
for (int i = 0; i <= n; i++)
g[i].clear();
memset(vis, 0, sizeof(vis));
int u, v, l;
for (int i = 1; i < n; i++) {//读入n-1条边
cin >> u >> v >> l;
g[u].push_back(Edge(v, l));
g[v].push_back(Edge(u, l));
}
f[0] = n;
root = 0;
totalNodes = n;
getroot(1, 0);
ans = 0;
work(root);
cout << ans << endl;
}
}
网友评论