| 题目名称 | 1714. [POJ1741][男人八题]树上的点对 |
|---|---|
| 输入输出 | poj1741_tree.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-09-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：177， 提交：500， 通过率：35.4% | ||||
 TA |
100 | 0.390 s | 19.96 MiB | C++ |
 AAAAAAAAAA |
100 | 0.439 s | 0.42 MiB | C++ |
 lemonalien |
100 | 0.484 s | 0.72 MiB | C++ |
 LGLJ |
100 | 0.485 s | 2.56 MiB | C++ |
 遥时_彼方 |
100 | 0.515 s | 4.90 MiB | C++ |
|
lemonalien |
100 | 0.516 s | 0.74 MiB | C++ |
|
lemonalien |
100 | 0.517 s | 0.74 MiB | C++ |
 前鬼后鬼的守护 |
100 | 0.520 s | 5.47 MiB | C++ |
|
lemonalien |
100 | 0.526 s | 0.74 MiB | C++ |
 Hzoi_Ivan |
100 | 0.527 s | 1.16 MiB | C++ |
| 关于 树上的点对 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
点分真的难
| ||||
|
改了半天点分治，最后发现是树的重心求错了。。。基础要掌握扎实啊。。。
| ||||
|
为什么我每天都在被卡常TT
| ||||
|
| ||||
|
%%%
| ||||
|
| ||||
|
| ||||
|
回复 @cstdio :
梦迪的代码有点小问题，他代码里面联通块的大小不是正确的，可能会影响复杂度。正确的做法应该在每次找到根之后再次dfs求子树大小。如果某次被数据卡掉了就尴尬了。 | ||||
|
OOOOOOrrrzzz___________
| ||||
|
边分治被卡了......
我说怎么搞的...找边写挂了...居然还有80分...... 改进了最坏复杂度的边分治比没改进的还慢......= = | ||||
Shirry
kemoto
可以的.
MistyEye
FoolMike
sxysxy
AntiLeaf1714. [POJ1741][男人八题]树上的点对
★★★ 输入文件：poj1741_tree.in
输出文件：poj1741_tree.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
给一棵有$n$个节点的树，每条边都有一个长度（小于$1001$的正整数）。
定义$dist(u,v)=$节点$u$到节点$v$的最短路距离。
给出一个整数$k$，我们称顶点对$(u,v)$是合法的当且仅当$dist(u,v)$不大于$k$。
写一个程序，对于给定的树，计算有多少对顶点对是合法的。
【输入格式】
输入包含多组数据。
每组数据的第一行有两个整数$N，K（N<=10000）$。接下来$N-1$行每行有三个整数$u,v,l$，代表节点$u$和$v$之间有一条长度$l$的无向边。
输入结束标志为$N=K=0$.
【输出格式】
对每组数据输出一行一个正整数，即合法顶点对的数量。
【样例输入】
5 4 1 2 3 1 3 1 1 4 2 3 5 1 0 0
【样例输出】
8
【来源】
男人八题 Problem E