题意翻译

给定一棵n个点的树,树上有m个黑点,求出一条路径,使得这条路径经过的黑点数小于等于k,且路径长度最大

Code:

#include <bits/stdc++.h>
using namespace std;
#define pr pair<int, int>
#define mp make_pair
const int maxn = 2000003;
const int inf = 1000000000;
void setIO(string a)
{
string in = a + ".in", out = a + ".out";
freopen(in.c_str(), "r", stdin);
}
vector <pr> vrr;
int edges, n, m, K, ans, mdep, tl, root = 0, sn;
int hd[maxn], to[maxn << 1], nex[maxn << 1], val[maxn << 1], siz[maxn];
int mk[maxn], vis[maxn], mine[maxn], dis[maxn], tmp1[maxn], tmp2[maxn], f[maxn];
void add(int u, int v, int c)
{
nex[++edges] = hd[u], hd[u] = edges, to[edges] = v, val[edges] = c;
}
void Getroot(int u, int ff)
{
siz[u] = 1, f[u] = 0;
for(int i = hd[u]; i ; i = nex[i])
{
int v = to[i];
if(v == ff || vis[v]) continue;
Getroot(v, u);
siz[u] += siz[v], f[u] = max(f[u], siz[v]);
}
f[u] = max(sn - siz[u], f[u]);
if(f[u] < f[root]) root = u;
}
void getmax(int x, int ff, int d1)
{
siz[x]=1;
mdep = max(mdep, d1 + mk[x]);
for(int i = hd[x]; i ; i = nex[i])
{
int v = to[i];
if(vis[v] || v == ff) continue;
dis[v] = dis[x] + val[i];
getmax(v, x, d1 + mk[x]);
siz[x]+=siz[v];
}
}
void getdis(int x, int ff, int d2)
{
if(d2 > K) return ;
tmp1[++tl] = dis[x], tmp2[tl] = d2 + mk[x];
for(int i = hd[x]; i ; i = nex[i])
{
int v = to[i];
if(v == ff || vis[v]) continue;
getdis(v, x, d2 + mk[x]);
}
}
void calc(int x)
{
if(mk[x]) --K;
vrr.clear();
siz[x]=1;
for(int i = hd[x]; i ; i = nex[i])
{
int v = to[i];
if(vis[v]) continue;
mdep = 0, dis[v] = val[i];
getmax(v, x, 0);
siz[x]+=siz[v];
vrr.push_back(mp(mdep, v));
}
sort(vrr.begin(), vrr.end());
tl = mine[0] = 0;
// printf("%d ::: ",x);
for(int sz = vrr.size(), i = 0; i < sz; ++i)
{
int cur = vrr[i].second;
int pdl = tl;
getdis(cur, x, 0);
for(int j = pdl + 1; j <= tl; ++j)
if(K >= tmp2[j])
ans = max(ans, mine[K - tmp2[j]] + tmp1[j]);
// printf("%d ",vrr[i].second);
// tmp2[j] :: 有tmp2[j]个黑子时的最大值.
for(int j = pdl + 1; j <= tl; ++j) mine[tmp2[j]] = max(mine[tmp2[j]], tmp1[j]);
for(int j = 1; j <= vrr[i].first; ++j) mine[j] = max(mine[j-1],mine[j]);
}
// printf("\n");
if(vrr.size())
for(int i=1;i<=vrr[vrr.size()-1].first;++i) mine[i] = -inf;
if(mk[x]) ++K;
}
void solve(int u)
{
vis[u] = 1;
calc(u);
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(vis[v]) continue;
root=0,sn=siz[v];
Getroot(v,u);
solve(root);
}
}
int main()
{
// setIO("input");
scanf("%d%d%d",&n, &K, &m);
for(int i = 1,o; i <= m ; ++i)
{
scanf("%d",&o);
mk[o] = 1;
}
for(int i = 1; i < n ; ++i)
{
int u, v, c;
scanf("%d%d%d",&u, &v, &c);
add(u, v, c), add(v, u, c);
}
for(int i=1;i<maxn;++i) mine[i]=-inf;
sn = n, f[0] = inf;
Getroot(1, 0); solve(root);
printf("%d\n",ans);
return 0;
}

  

最新文章

  1. ffmpeg 音频转换(amr2mp3)
  2. SQL镜像资料
  3. MTOM以及在WCF中的应用
  4. Android去除CPU占用过高时屏幕四周闪红框
  5. 《ruby编程语言》笔记 1
  6. xcode插件——新建cocos2dx工程
  7. servlet(jsp)中的重定向和转发
  8. JDK1.8源码阅读系列之一:ArrayList
  9. HDU 4008 Parent and son
  10. TCP/IP、Http、Socket的区别与关系
  11. 【Ansible】 基于SSH的远程管理工具
  12. sh 脚本执行sql文件传参数
  13. composer安装以及更新问题,配置中国镜像源。
  14. ios模拟器命令
  15. Apache Ant安装 验证
  16. Tomcat环境变量,端口号,编码格式,项目路径,默认页的配置
  17. redis PUB/SUB(发布/订阅)
  18. Google Drive 里的文件下载的方法
  19. python-day27--hashlib模块-摘要算法
  20. scala -- 递归 实现 斐波那契函数

热门文章

  1. Linux Container测试之block IO
  2. HDU 4258(Covered Walkway-斜率优化)
  3. HDU 5239 上海大都会 D题(线段树+数论)
  4. ZOJ 2314 无源汇可行流(输出方案)
  5. bzoj4004 [JLOI2015]装备购买——线性基+贪心
  6. Too-Java:Intellij Idea
  7. vmware centos7 没有网络设备
  8. mybatis中if标签判断字符串相等问题
  9. MSSQL:账号无法删除方案
  10. Web框架系列之Tornado