博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[洛谷P4178]Tree
阅读量:6519 次
发布时间:2019-06-24

本文共 1796 字,大约阅读时间需要 5 分钟。

题目大意:给一棵树,问有多少条路径长度小于等于$k$

题解:点分治

卡点:

 

C++ Code:

#include 
#include
#define maxn 40010const int inf = 0x3f3f3f3f;inline int max(int a, int b) {return a > b ? a : b;}int head[maxn], cnt;struct Edge { int to, nxt, w;} e[maxn << 1];inline void add(int a, int b, int c) { e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt; e[++cnt] = (Edge) {a, head[b], c}; head[b] = cnt;}bool vis[maxn];namespace Center_of_Gravity { int sz[maxn], __nodenum; int root, MIN; #define n __nodenum void __getroot(int u, int fa) { sz[u] = 1; int MAX = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa && !vis[v]) { __getroot(v, u); sz[u] += sz[v]; MAX = max(MAX, sz[v]); } } MAX = max(MAX, n - sz[u]); if (MAX < MIN) MIN = MAX, root = u; } int getroot(int u, int nodenum = 0) { n = nodenum ? nodenum : sz[u]; MIN = inf; __getroot(u, 0); return root; } #undef n}using Center_of_Gravity::getroot;int n, k, ans;int S[maxn], tot;void getlist(int u, int fa, int val) { if (val <= k) S[++tot] = val; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa && !vis[v]) getlist(v, u, val + e[i].w); }}int calc(int u, int val) { tot = 0; getlist(u, 0, val); std::sort(S + 1, S + tot + 1); int l = 1, r = tot, res = 0; while (l <= r) { if (S[l] + S[r] <= k) res += r - l, l++; else r--; } return res;}void solve(int u) { vis[u] = true; ans += calc(u, 0); for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (!vis[v]) { ans -= calc(v, e[i].w); solve(getroot(v)); } }}int main() { scanf("%d", &n); for (int i = 1, a, b, c; i < n; i++) { scanf("%d%d%d", &a, &b, &c); add(a, b, c); } scanf("%d", &k); solve(getroot(1, n)); printf("%d\n", ans); return 0;}

  

转载于:https://www.cnblogs.com/Memory-of-winter/p/9772619.html

你可能感兴趣的文章
stomp-php
查看>>
Mysql慢查询日志脚本
查看>>
python字典生成式
查看>>
WampServer下Apache配置vHost
查看>>
IOS 开发证书设置
查看>>
poj1328 -贪心雷达问题
查看>>
我的友情链接
查看>>
第柒章學習 Lisp 3rd Edition, Winston & Horn
查看>>
簡單使用 tshark 命令形的 wireshark tcpdump
查看>>
git 常用指令快速上手
查看>>
Struts2教程5:使用Validation框架验证数据
查看>>
监控网络丢包率脚本
查看>>
jQuery 对AMD的支持
查看>>
我的友情链接
查看>>
验证输入的邮件地址是否合法
查看>>
CentOS使用Smartmontools检测磁盘状态
查看>>
shell中$#等含义
查看>>
centos7 安装nbd
查看>>
Linux学习笔记(七)---CentOS7单用户模式
查看>>
bash脚本:函数
查看>>