这题数据范围变成了200000 n^2就过不了 同时要求求的是最少的边数 不能容斥

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + ;
const int MAXM = 2e5 + ;
int to[MAXM << ], nxt[MAXM << ], Head[MAXN], ed = ;
int cost[MAXM << ];
int ok[];
inline void addedge(int u, int v, int c) {
to[++ed] = v;
cost[ed] = c;
nxt[ed] = Head[u];
Head[u] = ed;
}
inline void ADD(int u, int v, int c) {
addedge(u, v, c);
addedge(v, u, c);
}
int n, anser, k, cnt;
int sz[MAXN], f[MAXN], dep[MAXN], sumsz, root;
bool vis[MAXN];
pair<int, int> o[MAXN];
int num[MAXN];
void getroot(int x, int fa) {
sz[x] = ;
f[x] = ;
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa || vis[v]) {
continue;
}
getroot(v, x);
sz[x] += sz[v];
f[x] = max(f[x], sz[v]);
}
f[x] = max(f[x], sumsz - sz[x]);
if (f[x] < f[root]) {
root = x;
}
}
void getdeep(int x, int fa, int deep) {
if (dep[x] > k) {
return;
}
o[++cnt] = make_pair(dep[x], deep);
num[++num[]] = dep[x];
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa || vis[v]) {
continue;
}
dep[v] = dep[x] + cost[i];
getdeep(v, x, deep + );
}
}
void calc(int x, int d) {
num[] = ;
dep[x] = d;
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (vis[v]) {
continue;
}
cnt = ;
dep[v] = dep[x] + cost[i];
getdeep(v, x, );
for (int j = ; j <= cnt; j++) {
if (o[j].first <= k) {
if (ok[k - o[j].first] != INT_MAX) {
anser = min(anser, ok[k - o[j].first] + o[j].second);
}
}
}
for (int j = ; j <= cnt; j++) {
if (o[j].first <= k) {
ok[o[j].first] = min(o[j].second, ok[o[j].first]);
}
}
}
for (int i = ; i <= num[]; i++) {
ok[num[i]] = INT_MAX;
}
}
void solve(int x) {
vis[x] = ;
calc(x, );
int totsz = sumsz;
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (vis[v]) {
continue;
}
root = ;
sumsz = sz[v] > sz[x] ? totsz - sz[x] : sz[v];
getroot(v, );
solve(root);
}
}
int main() {
scanf("%d %d", &n, &k);
anser = INT_MAX;
for (int i = ; i <= k; i++) {
ok[i] = INT_MAX;
}
cnt = ;
memset(Head, , sizeof(Head));
memset(vis, , sizeof(vis));
ed = ;
int u, v, c;
for (int i = ; i < n; i++) {
scanf("%d %d %d", &u, &v, &c);
ADD(u + , v + , c);
}
root = , sumsz = f[] = n;
getroot(, );
solve(root);
printf("%d\n", anser == INT_MAX ? - : anser);
return ;
}

注意dep[x]>k的时候要return 不然会re

最新文章

  1. [译]libev和libevent的设计差异
  2. redis 学习 01(下载 学习资源)
  3. 【BZOJ-4522】密钥破解 数论 + 模拟 ( Pollard_Rho分解 + Exgcd求逆元 + 快速幂 + 快速乘)
  4. web中session与序列化的问题
  5. PAT乙级 1028. 人口普查(20)
  6. Myeclipse优化篇
  7. 再起航,我的学习笔记之JavaScript设计模式01
  8. css 块元素、内联元素、内联块元素
  9. jquery学习-document.ready和document.onload区别
  10. PHP中new static()与new self()的区别异同分析
  11. vijos 1605 双栈排序 - 贪心 - 二分图
  12. 一个类似于jq的小型库
  13. 洛谷P3868 [TJOI2009]猜数字(中国剩余定理,扩展欧几里德)
  14. TCGA phenotype各列的含义
  15. centos shell编程3【告警系统】 没有服务器端和客户端的概念 main.sh mon.conf load.sh 502.sh mail.php mail.sh disk.sh 第三十七节课
  16. Mybatis中的几种注解映射
  17. 如何实现php异步处理
  18. LDA算法里面Dirichlet分布的两个参数alpha和beta怎样确定?
  19. HighCharts 在IE8下饼图不显示的问题
  20. 经典C#面试题

热门文章

  1. 【DSP开发】DSP程序优化
  2. java8函数式接口(Functional Interface)
  3. day16 模块导入及环境变量
  4. [Agc036D]Do Not Duplicate_链表_贪心_数论
  5. Redis(1.11)Redis4.0.11 cluster 分布式集群搭建
  6. 对Redis 单进程、单线程模型的理解(网摘)
  7. 了解WebSocket
  8. golang 环境配置 over centos7
  9. Hystrix服务容错保护
  10. Java EE javax.servlet中的RequestDispatcher接口