给出N(1<=N<=200000)个结点的树,求长度等于K(1<=K<=1000000)的路径的最小边数。
点分治,这道题目和POJ 2114很接近,2114是求是否存在长度为K的边,但是那个K比较大。但是这道题目的K比之小了10倍。
1. 用V[i]表示到当前树根root的路径长度为i 时的点(赋值为root结点即可),这样就可以用来判断两条到根的路径长度之和是否等于K:
结点a的root的距离为i,结点b到root的距离为j,处理完a之后会得到V[i] = root,那么在处理结点b的时候,如果V[K-j] = root,就说明某一个a和b的路径长度为K,此时,就可以更新最小边数了。
2. e[i]表示到当前树根root的路径长度为i 时的边的最小条数。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define N 200010
#define inf 0x3f3f3f3f
struct node {
int v, l;
node() {}
node(int _v, int _l): v(_v), l(_l) {};
};
vector<node> g[N];
int n, K, cur, root, size, ans;
int s[N], f[N], d[N], e[N]; //s子树的结点数,f求重心,d子结点到根的距离,e子结点到根的边数
int v[N*10], c[N*10];
bool done[N];
void getroot(int now, int fa) {
int u;
s[now] = 1, f[now] = 0;
for (int i=0; i<g[now].size(); i++)
if ((u = g[now][i].v) != fa && !done[u]) {
getroot(u, now);
s[now] += s[u];
f[now] = max(f[now], s[u]);
}
f[now] = max(f[now], size-s[now]);
if (f[now] < f[root]) root = now;
}
void dfs1(int now, int fa) {
if (d[now] > K) return ;
if (v[K-d[now]] == cur) ans = min(ans, c[K-d[now]]+e[now]);
int u;
for (int i=0; i<g[now].size(); i++)
if ((u = g[now][i].v) != fa && !done[u]) {
d[u] = d[now] + g[now][i].l;
e[u] = e[now] + 1;
dfs1(u, now);
}
}
void dfs2(int now, int fa) {
if (d[now] > K) return ;
if (v[d[now]] != cur) {
c[d[now]] = e[now];
v[d[now]] = cur;
} else c[d[now]] = min(c[d[now]], e[now]);
int u;
for (int i=0; i<g[now].size(); i++)
if ((u = g[now][i].v) != fa && !done[u])
dfs2(u, now);
}
void work(int now) {
v[0] = cur = now + 1;
int u;
for (int i=0; i<g[now].size(); i++)
if (!done[u = g[now][i].v]) {
d[u] = g[now][i].l;
e[u] = 1;
dfs1(u, now);
dfs2(u, now);
}
getroot(now, n); //更新s数组
done[now] = true;
for (int i=0; i<g[now].size(); i++)
if (!done[u = g[now][i].v]) {
f[n] = size = s[u];
getroot(u, root=n);
work(root);
}
}
int main() {
scanf("%d%d", &n, &K);
for (int i=0; i<=n; i++) g[i].clear();
for (int i=1, a, b, c; i<n; i++) {
scanf("%d%d%d", &a, &b, &c);
g[a].push_back(node(b, c));
g[b].push_back(node(a, c));
}
memset(done, false, sizeof(done));
ans = f[n] = size = n;
getroot(0, root=n);
work(root);
printf("%d\n", ans < n ? ans : -1);
return 0;
}
分享到:
相关推荐
(自己写的动态点分治巨垃圾,常数是别人的两倍) 用动态开点线段树死活过不去,学了一波大佬用 vector 开树状数组立马就卡过去了 考虑点分树的做法,在点分树上每个点以距离为下标建一棵线段树,每次询问查询子树的...
CTSC 2011 无穷图的桥(BZOJ 2307) 题解.ppt
BZOJ原题-BZOJP1000-P2000的题目,下载后可以离线做题。
八中OJ,又简作BZOJ,以原题巨多而著称,该数据为BZOJ上的1000-1109和1130-1139的测试数据节点,没有题目,有需要题目的可以到https://hydro.ac/d/bzoj/p网站查找对应的题目。
BZOJ原题-BZOJP3001-P4000的题目,下载后可以离线做题。
bzoj部分数据.
BZOJ3230相似子串的测试数据,希望能够帮到大家。
BZOJ原题-BZOJP2001-P3000的题目,下载后可以离线做题。
BZOJ网站镜像,对于经常挂掉的BZOJ真是刷题必备啊!
BZOJ原题-BZOJP4001-P4406的题目,下载后可以离线做题。
BZOJ平台全部代码,解压到一个文件夹在打开使用。BZOJ平台全部代码,解压到一个文件夹在打开使用。
题解 , 文档 , 资料 BZOJ 泡泡堂
BZOJ省选十连测题面,只有题面!!!!!,请自行到BZOJ上进行提交,上传目的是提供离线的一个题目
ZOJCH是BZOJ题库的离线版
bzoj1878数据(莫队)详细题解:http://blog.csdn.net/boyxiejunboy/article/details/50611972
「BZOJ1053」反素数/「Violet5」樱花 详细题解
CreationAugust 的BZOJ代码合集 【Written by CreationAugust】
八中OJ所有题目
bzoj FFT 的模版
Description 背景 众所周知,DZY是个大学霸,精通数理化。有天,吉丽拿着一道物理题目去问DZY,DZY很快就秒了这题,但是懒得算了,就让你来解决它。 题目描述 现在水平面上有一条无限长的光滑轨道,上面有n个小球...