「BZOJ1782」[Usaco2010 Feb] slowdown慢慢游

2014年5月18日2,7480

Description

每天Farmer John的N头奶牛(1 <= N <= 100000，编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树，粮仓在1号牧场。恰好有N-1条道路直接连接着牧场，使得牧场之间都恰好有一条路径相连。第i条路连接着A_i，B_i，(1 <= A_i <= N; 1 <= B_i <= N)。奶牛们每人有一个私人牧场P_i (1 <= P_i <= N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛1离开，前往P_1；然后是奶牛2，以此类推。当奶牛i走向牧场P_i时候，他可能会经过正在吃草的同伴旁。当路过已经有奶牛的牧场时，奶牛i会放慢自己的速度，防止打扰他的朋友。考虑如下的牧场结构（括号内的数字代表了牧场的所有者）。

Input

* 第1行 : 一个正整数N * 第2…N行: 第i+1行包括一对正整数A_i,B_i * 第N+1..N+N行: 第 N+i行包括一个正整数: P_i

Output

* 第一行到第N行：第i行表示第i只奶牛需要被放慢的次数

Sample Input

5
1 4
5 4
1 3
2 4
4
2
1
5
3

Sample Output

0
1
0
2
1

题解

第一次做这种题感觉脑洞大开

可以发现一只牛到达后，以他为根的一整棵子树都要+1，可用树状数组或者线段树来维护这一操作

具体方法也很多

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,cnt;
int p[N],ans[N],head[N],t[N];
struct data{int to,next;}e[N+N];
void ins(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v)
{ins(u,v);ins(v,u);}
inline int lowbit(int x){return x&(-x);}
void update(int x,int val)
{for(int i=x;i<=n;i+=lowbit(i))t[i]+=val;}
int ask(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i))
        sum+=t[i];
    return sum;
}
void dfs(int x,int fa)
{
    ans[p[x]]=ask(p[x]);
    update(p[x],1);
    for(int i=head[x];i;i=e[i].next)
        if(e[i].to!=fa)
            dfs(e[i].to,x);
    update(p[x],-1);
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
        insert(read(),read());
    for(int i=1;i<=n;i++)
        p[read()]=i;
    dfs(1,0);
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 100005

using namespace std;

inline int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int n,cnt;

int p[N],ans[N],head[N],t[N];

struct data{int to,next;}e[N+N];

void ins(int u,int v)

{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}

void insert(int u,int v)

{ins(u,v);ins(v,u);}

inline int lowbit(int x){return x&(-x);}

void update(int x,int val)

{for(int i=x;i<=n;i+=lowbit(i))t[i]+=val;}

int ask(int x)

{

int sum=0;

for(int i=x;i>0;i-=lowbit(i))

sum+=t[i];

return sum;

}

void dfs(int x,int fa)

{

ans[p[x]]=ask(p[x]);

update(p[x],1);

for(int i=head[x];i;i=e[i].next)

if(e[i].to!=fa)

dfs(e[i].to,x);

update(p[x],-1);

}

int main()

{

n=read();

for(int i=1;i<n;i++)

insert(read(),read());

for(int i=1;i<=n;i++)

p[read()]=i;

dfs(1,0);

for(int i=1;i<=n;i++)

printf("%d\n",ans[i]);

return 0;

}

« 「BZOJ2743」[HEOI2012] 采花「BZOJ1537」[POI2005] Aut – The Bus »

hzwer.com _ Home | http://hzwer.com

「BZOJ1782」[Usaco2010 Feb] slowdown慢慢游

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论