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

ydc的博客

 
 
 

日志

 
 

bzoj 3031  

2013-02-05 13:25:21|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

runaway

听现场切的天哥讲了做法之后改了,但不够完美。

在linux下是可以过的,在windows下却会栈溢出,因为linux的系统栈比windows大一些

不过天哥的在windows下也无压力。

反正bzoj是linux环境,所以我就过了……

大概讲一下算法吧

假设F[i]表示对i而言的答案

F[i]=1+sigma{F[j]}(j是i的儿子)-能走到i的儿子又不能走到i的点的数量

关键是怎么统计最后那个值(就是一串中文组成的那个东东)

采用逆向思维的办法,对于点p,找到p往上走最近的走不到的点q,F[q]--,这就可以了

找的过程用二分查找

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 200010
using namespace std;
typedef long long LL;
int n,sum[MAXN],stack[MAXN],top,F[MAXN];
LL dis[MAXN],L,len[MAXN];
int tot,num[MAXN],next[MAXN],start[MAXN];
void make(int a,int b,LL c){  tot++,num[tot]=b,next[tot]=start[a],len[tot]=c,start[a]=tot;  }
void read()
{
    scanf("%d %lld",&n,&L);
    for(int i=2,father;i<=n;i++)
    {
        LL L;
        scanf("%d %lld",&father,&L);
        make(father,i,L);
    }
}
int Two(int l,int r,LL d)
{
    if(dis[stack[r]]<d)  return stack[r];
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(dis[stack[mid]]<d)  l=mid+1;
        else r=mid;
    }
    return stack[l-1];
}
void DFS(int p)
{
    F[p]=1,stack[++top]=p;
    for(int i=start[p];i;i=next[i])
    {
        int q=num[i];
        dis[q]=dis[p]+len[i],DFS(q),F[p]+=F[q];
        if(dis[q]>L)  F[Two(1,top,dis[q]-L)]--;
    }
    top--;
}
void print()
{
    for(int i=1;i<=n;i++)
        printf("%d\n",F[i]);
}
int main()
{
    read();
    DFS(1);
    print();
    return 0;
}
  评论这张
 
阅读(201)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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