1131: [POI2008]Sta
1779: [Usaco2010 Hol]Cowwar 奶牛战争

3011: [Usaco2012 Dec]Running Away From the Barn

高橋直樹 posted @ 2013年3月21日 20:03 in BZOJ with tags bzoj usaco , 785 阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=3011

RunID User Problem Result Memory Time Language Code_Length Submit_Time
370535 Liu_Ts 3011 Accepted 14804 kb 908 ms C++ 1039 B 2013-03-17 23:35:13

 

题意

给出以1号点为根的一棵有根树,问每个点的子树中与它距离小于L的点有多少个。

题解

dfs,对于每个点,打一个+1的标记,在从它到根的路径上,第一个大于>L的点打一个-1的标记,

则每个点的答案就是以它为根的子树的标记和。

官方题解写的倍增,我只会记录dfs序列,然后二分。

 

#include<cstring>
#include<cmath>
#include<climits>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=210000;
int v[N],next[N],head[N],n,k; ll len,w[N];
int f[N],stack[N],tot;ll s[N];
void build(int x,int y,ll z)
{
    v[++k]=y;w[k]=z;next[k]=head[x];head[x]=k;
}
 
int check(int r)
{
    ll l=1;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(s[stack[tot]]-s[stack[mid]]>len) l=mid;
        else r=mid-1;
    }
    return stack[l];
}
 
void dfs(int x,ll sum)
{
    stack[++tot]=x;s[x]=sum;
    f[x]+=1;f[check(tot)]-=1;
    for(ll i=head[x];i;i=next[i])
    {
        dfs(v[i],sum+w[i]);
        f[x]+=f[v[i]];
    }
    tot--;
}
 
int main()
{
    scanf("%d%lld",&n,&len);
    for(int i=2;i<=n;i++)
    {
        ll x,y;scanf("%d%lld",&x,&y);
        build(x,i,y);
    }
    s[0]=-ll(1e20);stack[++tot]=0;
    dfs(1,0);
    for(int i=1;i<=n;i++)
        printf("%d\n",f[i]);
}
蒟蒻 说:
2016年10月21日 15:10

您维护的队列好像不是单调的 为什么可以直接用二分


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter