poj 1741 Tree(树的点分治)
2024-08-26 04:08:37
poj 1741 Tree(树的点分治)
给出一个n个结点的树和一个整数k,问有多少个距离不超过k的点对。
首先对于一个树中的点对,要么经过根结点,要么不经过。所以我们可以把经过根节点的符合点对统计出来。接着对于每一个子树再次运算。如果不用点分治的技巧,时间复杂度可能退化成\(O(n^2)\)(链)。如果对于子树重新选根,找到树的重心,就一定可以保证时间复杂度在\(O(nlogn)\)内。
具体技巧是:首先选出树的重心,将重心视为根。接着计算出每个结点的深度,以此统计答案。由于子树中可能出现重复情况,需要在子树中相应的减去一部分ans。具体实现在代码中。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e4+5;
struct Graph{
struct Edge{
int to, next, v; Graph *bel;
Edge& operator ++(){
return *this=bel->edge[next]; }
}edge[maxn*2];
int cntedge, fir[maxn];
void addedge(int x, int y, int v){
Edge &e=edge[++cntedge];
e.to=y; e.next=fir[x]; e.v=v;
fir[x]=cntedge; e.bel=this;
}
Edge& getlink(int x){ return edge[fir[x]]; }
void RESET(){ cntedge=0; memset(fir, 0, sizeof(fir)); }
}g;
int n, k, size[maxn], w[maxn], dep[maxn];
int cnt[maxn], tail;
bool done[maxn];
//获取子树大小
int getsize(int now, int par, int num){
size[now]=0; w[now]=0;
Graph::Edge e=g.getlink(now);
for (; e.to; ++e){
if (e.to==par||done[e.to]) continue;
size[now]+=getsize(e.to, now, num);
w[now]=max(w[now], size[e.to]);
}
++size[now]; w[now]=max(w[now], num-size[now]);
return size[now];
}
//获取根的位置
int getroot(int now, int par){
Graph::Edge e=g.getlink(now);
int root=now, tmp=now;
for (; e.to; ++e){
if (e.to==par||done[e.to]) continue;
tmp=getroot(e.to, now);
if (w[tmp]<w[root]) root=tmp; //mdzzle
}
return root;
}
//获取子树中结点深度,并创造深度数组
void getdep(int now, int par, int step){
Graph::Edge e=g.getlink(now);
for (; e.to; ++e)
if (e.to!=par&&!done[e.to])
getdep(e.to, now, step+e.v);
dep[now]=step;
cnt[tail++]=step;
}
//通过深度数组统计和小于等于k的数对
int getans(int k, int tail){
sort(cnt, cnt+tail);
--tail; int ans=0;
for (int l=0; l<tail; ++l){
while (cnt[l]+cnt[tail]>k&&l<tail) --tail;
ans+=tail-l;
}
return ans;
}
int solve(int now, int num){
getsize(now, 0, num); //获取当前树的子树大小
if (size[now]==1) return 0;
now=getroot(now, 0); //凭借子树大小找到重心
tail=0; //把深度数组复原
getdep(now, 0, 0); //获取每个结点的深度,构建深度数组
//获取答案,别忘记减掉重复的点对
int ans=getans(k, tail);
done[now]=true; //堵住当前点
Graph::Edge e=g.getlink(now);
for (; e.to; ++e) if (!done[e.to]){
tail=0; getdep(e.to, 0, 0);
ans-=getans(k-e.v*2, tail);
ans+=solve(e.to, size[e.to]);
}
return ans;
}
int main(){
while (~scanf("%d%d", &n, &k)&&n&&k){
int t1, t2, t3; g.RESET();
for (int i=1; i<=n; ++i) done[i]=false;
for (int i=1; i<n; ++i){
scanf("%d%d%d", &t1, &t2, &t3);
g.addedge(t1, t2, t3);
g.addedge(t2, t1, t3);
}
printf("%d\n", solve(1, n));
}
return 0;
}
最新文章
- 【JavaScript】冒泡排序,字符串排序,数字排序
- TypeScript &; JavaScript
- linux 下搭建svn
- Android之ADB指令
- 【循序渐进学Python】1. Python基础知识
- html-javascript前端页面刷新重载的方法汇总
- (续篇3):飞测独家のJmeter秘籍,限量发放
- DLL入门浅析(3)——从DLL中导出变量
- ext3文件系统目录限制问题
- java-两个jre目录和三个lib目录-转
- windows和linux双系统修改启动项
- hdfs文件系统架构详解
- WebGL光照阴影映射
- PHP中put和post区别
- 逆向工程-获得IPsearch的注册码
- Linux CPU占用率监控工具小结
- pycaffe训练的完整组件示例
- 025 如何利用github绑定自己的域名
- Rodrigues(罗德里格斯)旋转公式推导
- HttpURLConnection 返回汉字乱码(全是问号)
热门文章
- HTML5 学习记录——0
- django中使用多个数据库,跨库查询
- 如何在node.js中使用neo4j
- Java_基础_01_static和final
- 谈MicroMessageTest的开始创建
- leetcode 3 Longest Substring Without Repeating Characters(滑动窗口)
- 【leetcode刷题笔记】Longest Consecutive Sequence
- resin启动时报错com.caucho.config.LineConfigException的解决
- NOIP 2011 DAY 2
- CQOI2018做题记录