设为首页 加入收藏

TOP

POJ 2114 Boatherds[Tree,点分治]
2014-11-23 19:18:59 来源: 作者: 【 】 浏览:5
Tags:POJ 2114 Boatherds Tree 分治

求一棵树上是否存在路径长度为K的点对。

POJ 1714求得是路径权值<=K的路径条数,这题只需要更改一下统计路径条数的函数即可,如果最终的路径条数大于零,则说明存在这样的路径。

刚开始我以为只要在分治过程中出现过长度为K的就算是找到了,其实不然,因为可能是相同子树里面的两个结点,这个结果显然是错误的。

#include 
#include 
#include 
#include 
using namespace std;
struct node {
    int v, l;
    node() {};
    node(int _v, int _l):v(_v), l(_l) {};
};
#define N 10015
int n, m, K, size, root, s[N], f[N], d[N], ans;
bool done[N], ok;
vector dep;
vector g[N];

void getroot(int now, int fa) {
    int u;
    s[now] = 1; f[now] = 0;
    for (int i=0; i 
 

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇每日一水 POJ8道水题 下一篇POJ 1743 Musical Theme(后缀数..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·求navicat for mysql (2025-12-26 13:21:33)
·有哪位大哥推荐一下m (2025-12-26 13:21:30)
·MySQL下载与安装教程 (2025-12-26 13:21:26)
·Linux_百度百科 (2025-12-26 12:51:52)
·Shell 流程控制 | 菜 (2025-12-26 12:51:49)