注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

bzoj 3320 seq 点分治+队列  

2014-06-11 16:14:22|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
好久没写数据结构类题了 刚好做的一套题(似乎是去年HN集训)中有一道不错的点分治的题 便决定在做完之后把这题改改
由于很久没写点分治 遍先打了一个第一问n^2,第二问n的暴力 然后发现可以卡着时过6个点
最后 在把点分治模板题——<=k路径数 重写了一遍后 便有信心写这题了(毕竟题解中说这是“noip难度”的题)
这题只要通过那道模板题(<=k路径数)稍稍改下就可以了 只要注意两点即可
1 权值要从边上改为点上
2 贡献值要在calc函数中顺便更新
点分治后面队列就比较简单了 想到就能写出来了
还有一些细节可以参考代码——以下通过lwher菊苣的点分治模板改写的 似乎常数很小的说
(复杂度O(nlogn)+O(n))

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int N=100010,BIG=1000000000,M=100000;
struct D
{
int dist,num;
}di[N];
int firste[N],nexte[N<<1],v[N<<1],w[N];
int sz[N],lim[N],b[N],numq[N],cnt[N<<1];
bool vis[N];
int n,e=0,root,tot,md,sum,allnum=0,ans=0;
bool cmp(D aa,D bb)
{
return aa.dist<bb.dist;
}
void build_edge(int x,int y)
{
++e;
nexte[e]=firste[x];
firste[x]=e;
v[e]=y;
}
void getroot(int u,int fa)
{
sz[u]=1;
lim[u]=0;
for(int p=firste[u];p;p=nexte[p])
if(v[p]!=fa&&!vis[v[p]])
{
getroot(v[p],u);
sz[u]+=sz[v[p]];
lim[u]=imax(lim[u],sz[v[p]]);
}
lim[u]=imax(lim[u],sum-sz[u]);
if(lim[u]<lim[root])root=u;
}
void getdist(int u,int fa,int d)
{
di[++tot].dist=d;
di[tot].num=u;
for(int p=firste[u];p;p=nexte[p])
if(v[p]!=fa&&!vis[v[p]])
getdist(v[p],u,d+w[v[p]]);
}
void calc(int u,int d,int dt)
{
tot=0;
getdist(u,0,0);
int res=0;
rep(i,tot)
cnt[M+di[i].dist+d]+=dt;
rep(i,tot)
{
numq[di[i].num]+=cnt[M-di[i].dist];
allnum-=cnt[M-di[i].dist];
}
rep(i,tot)
cnt[M+di[i].dist+d]-=dt;
}
void getans(int u)
{
calc(u,w[u],1);
vis[u]=1;
for(int p=firste[u];p;p=nexte[p])
if(!vis[v[p]])
{
calc(v[p],w[u]+w[v[p]]*2,-1);
sum=sz[v[p]];
lim[0]=sum;
root=0;
getroot(v[p],0);
getans(root);
}
}
int main()
{
int x,y;
scanf("%d",&n);
rep(i,n)
{
scanf("%d",&w[i]);
if(!w[i])--w[i];
}
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
build_edge(x,y);
build_edge(y,x);
}
rep(i,n)
scanf("%d",&b[i]);
root=0;
lim[0]=n;
sum=n;
getroot(1,0);
getans(root);
allnum/=2;
int j=0;
rep(i,n)
{
while(allnum<=0&&j<n)
{
++j;
allnum+=numq[b[j]];
}
if(allnum>0)
ans+=n-j+1;
else break;
allnum-=numq[b[i]];
}
printf("%d",ans);
return 0;
}



  评论这张
 
阅读(243)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017