题目链接

一道神奇的点分治

貌似有很多做法,我觉得BIT要好些一些(雾

要求经过黑点数<k就用BIT区间查询前缀

对于每个点用  BIT[0,k-经过黑点数]的最大值+路径长度

使用点分治做到O(n*log22n)

貌似还有O(nlog2n)的做法(雾

 #include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define rre(i,r,l) for(int i=(r);i>=(l);i--)
#define re(i,l,r) for(int i=(l);i<=(r);i++)
#define Clear(a,b) memset(a,b,sizeof(a))
#define inout(x) printf("%d",(x))
#define douin(x) scanf("%lf",&x)
#define strin(x) scanf("%s",(x))
#define LLin(x) scanf("%lld",&x)
#define op operator
#define CSC main
typedef unsigned long long ULL;
typedef const int cint;
typedef long long LL;
using namespace std;
cint inf=;
void inin(int &ret)
{
ret=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=;ch=getchar();}
while(ch>=''&&ch<='')ret*=,ret+=ch-'',ch=getchar();
ret=f?-ret:ret;
}
int head[],next[],zhi[],w[],si[],v[],ed;
int shu[],dis[],col[],bo[];
int cc[],t[];
int n,m,k,sum,ans,root,T;
void add(int a,int b,int c)
{
next[++ed]=head[a],head[a]=ed,zhi[ed]=b,v[ed]=c;
next[++ed]=head[b],head[b]=ed,zhi[ed]=a,v[ed]=c;
}
void getroot(int x,int fa)
{
w[x]=,si[x]=;
for(int i=head[x];i;i=next[i])if(!bo[zhi[i]]&&zhi[i]!=fa)
{
getroot(zhi[i],x);
si[x]+=si[zhi[i]];
w[x]=max(w[x],si[zhi[i]]);
}
w[x]=max(w[x],sum-si[x]);
if(w[x]<w[root])root=x;
}
int lowbit(int x){return x&-x;}
int query(int r)
{
int ret=-inf;r++;
while(r)
{
if(t[r]==T)ret=max(ret,cc[r]);
r-=lowbit(r);
}
return ret;
}
void add_(int c,int x)
{
c++;
while(c<=k+)
{
if(t[c]==T)cc[c]=max(cc[c],x);
else t[c]=T,cc[c]=x;
c+=lowbit(c);
}
}
void getans(int x,int fa)
{
if(shu[x]-col[root]>k)return ;
int hh=query(k-shu[x]+col[root]);
if(hh!=-inf)ans=max(ans,hh+dis[x]);
for(int i=head[x];i;i=next[i])if(!bo[zhi[i]]&&zhi[i]!=fa)
dis[zhi[i]]=dis[x]+v[i],shu[zhi[i]]=col[zhi[i]]+shu[x],getans(zhi[i],x);
}
void add(int x,int fa)
{
if(shu[x]-col[root]>k)return ;
add_(shu[x],dis[x]);
for(int i=head[x];i;i=next[i])if(!bo[zhi[i]]&&zhi[i]!=fa)
add(zhi[i],x);
}
void solve(int x)
{
T++;
bo[x]=;add_(col[x],);
for(int i=head[x];i;i=next[i])if(!bo[zhi[i]])
{
shu[zhi[i]]=col[x]+col[zhi[i]],dis[zhi[i]]=v[i];
getans(zhi[i],x);
add(zhi[i],x);
}
for(int i=head[x];i;i=next[i])if(!bo[zhi[i]])
root=,sum=si[zhi[i]],getroot(zhi[i],),solve(root);
}
int CSC()
{
inin(n),inin(k),inin(m);
re(i,,m)
{
int x;inin(x);
col[x]=;
}
re(i,,n)
{
int q,w,e;
inin(q),inin(w),inin(e);
add(q,w,e);
}
w[]=sum=n;
getroot(,);
re(i,,k+)cc[i]=-inf;
ans=-inf;
solve(root);
printf("%d",max(ans,));
return ;
}

最新文章

  1. UESTC 1546 Bracket Sequence
  2. NBOJv2 1004 蛤玮打扫教室(线段树区间更新区间最值查询)
  3. 深入解析hasOwnProperty与isPrototypeOf
  4. typename使用在模板中区分static成员和类型
  5. ButterKnife的使用
  6. 构建安全的Xml Web Service系列之初探使用Soap头
  7. dva + antd + mockjs 实现基础用户管理
  8. C++windows内核编程笔记day09_day10,对话框和窗体基本控件等的使用
  9. HashMap与HashTable面试宝典
  10. Updating and Publishing a NuGet Package - Plus making NuGet packages smarter and avoiding source edits with WebActivator
  11. Topographic ICA as a Model of Natural Image Statistics(作为自然图像统计模型的拓扑独立成分分析)
  12. nginx面试中最常见的18道题
  13. getHibernateTemplate()的用法 (转)
  14. iOS开发-自动隐藏键盘及状态栏
  15. Docker for Mac 安装及Mysql安装使用
  16. 使用webstorm创建vue项目
  17. 关于DP和背包
  18. [tools]python的mkdocs模块分分钟将md搞成一个网站
  19. php \r \n 和 &lt;br/&gt; \t
  20. Mac 下安装 ruby 环境解决 brew 安装 yarn 问题

热门文章

  1. springMVC去掉静态资源的拦截
  2. 通过JS模拟select表单,达到美化效果[demo][转]
  3. 爬虫自动登陆GitHub
  4. HDU 2602 - Bone Collector - [01背包模板题]
  5. HDU 4848 - Wow! Such Conquering!
  6. Pandas新建一个DataFrame
  7. xp上使用vsphere client报错问题
  8. JavaScript中的对象描述符(属性特性)
  9. 使用Maven导出项目依赖的jar包
  10. JAVA 的wait(), notify()与synchronized同步机制