USACO[Elite 2010 February Competition/gold]slowdown

起初一直纠结如何一一的将每头奶牛到达P[i]的停顿时间求出来，后来才发觉思路没对。

正确的做法是直接DFS搜到一个点就求到它所需的停顿时间。

具体做法：

设path为DFS过程中的栈，那么某个点的停顿时间就等于在这个栈中有几个牧场的所有者比当前牧场的所有者先出栏。

例如，对于上图（样例），如果出栏顺序为42153。

那么我们开始DFS，首先到1，栈：[1]，栈中没有比当前节点1先出栏的，所以到1这个牧场的牛无需停顿。

然后到4，栈：[1,4]，栈中没有比当前节点4先出栏的，所以到4这个牧场的牛无需停顿。

然后到2，栈：[1,4,2]，栈中比当前节点2先出栏的只有一个(4)，所以到2这个牧场的牛需停顿1次。

然后栈pop一下变成[1,4]。

然后到5，栈：[1,4,5]，栈中比当前节点5先出栏的有两个(1和4)，所以到5这个牧场的牛需停顿2次。

然后栈pop一下变成[1,4]，再pop一下，变成[1]。

然后到3，栈：[1,3]，在3前出栏的有一个(1)，所以到3这个牧场的牛需停顿1次。

所以输出：

0

1

0

2

1

具体实现有用到线段树。

CODE:

/*

PROG: slowdown

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-22

DESCRIPTION:

TITLE: Slowing down [Jelle van den Hooff, 2010]

CONTENT:

Every day each of Farmer John’s N (1 <= N <= 100,000) cows conveniently

numbered 1..N move from the barn to her private pasture. The pastures

are organized as a tree, with the barn being on pasture 1. Exactly

N-1 cow unidirectional paths connect the pastures; directly connected

pastures have exactly one path. Path i connects pastures A_i and

B_i (1 <= A_i <= N; 1 <= B_i <= N).

Cow i has a private pasture P_i (1 <= P_i <= N). The barn’s small

door lets only one cow exit at a time; and the patient cows wait

until their predecessor arrives at her private pasture. First cow

1 exits and moves to pasture P_1. Then cow 2 exits and goes to

pasture P_2, and so on.

While cow i walks to P_i she might or might not pass through a

pasture that already contains an eating cow. When a cow is present

in a pasture, cow i walks slower than usual to prevent annoying her

friend.

Consider the following pasture network, where the number between

parentheses indicates the pastures’ owner.

        1 (3)       

       / \

  (1) 4   3 (5)

     / \  

(2) 2   5 (4)

First, cow 1 walks to her pasture:

        1 (3)       

       / \

  [1] 4*  3 (5)

     / \  

(2) 2   5 (4)

When cow 2 moves to her pasture, she first passes into the barn’s

pasture, pasture 1. Then she sneaks around cow 1 in pasture 4 before

arriving at her own pasture.

        1 (3)

       / \

  [1] 4*  3 (5)

     / \  

[2] 2*  5 (4)

Cow 3 doesn’t get far at all — she lounges in the barn’s pasture, #1.

        1* [3]

       / \

  [1] 4*  3 (5)

     / \  

[2] 2*  5 (4)

Cow 4 must slow for pasture 1 and 4 on her way to pasture 5:

        1* [3]

       / \

  [1] 4*  3 (5)

     / \  

[2] 2*  5* [4]

Cow 5 slows for cow 3 in pasture 1 and then enters her own private pasture:

        1* [3]

       / \

  [1] 4*  3*[5]

     / \  

[2] 2*  5* [4]

FJ would like to know how many times each cow has to slow down.

PROBLEM NAME: slowdown

INPUT FORMAT:

* Line 1: Line 1 contains a single integer: N

* Lines 2..N: Line i+1 contains two space-separated integers: A_i and

        B_i

* Lines N+1..N+N: line N+i contains a single integer: P_i

SAMPLE INPUT (file slowdown.in):

5

1 4

5 4

1 3

2 4

4

2

1

5

3

OUTPUT FORMAT:

* Lines 1..N: Line i contains the number of times cow i has to slow

        down.

SAMPLE OUTPUT (file slowdown.out):

0

1

0

2

1

*/

#include <stdio.h>

#include <vector>

using std::vector;

 

const int MAXN=100000;

int N;

int A[MAXN-1],B[MAXN-1];

int P[MAXN];

vector<int> children[MAXN+1];

int order[MAXN+1];

int counter[MAXN+1];

int segment_tree[MAXN<<2];

 

int ask(int pos,int L,int R,int root=1)

{

    if (/*0<=L&&*/R<=pos) return segment_tree[root];

    int LL=L,LR=(L+R)>>1,Lroot=root<<1;

    int RL=LR+1,RR=R,Rroot=Lroot|1;

    int get=0;

    if (!(/*LR<0||*/pos<LL))

       get+=ask(pos,LL,LR,Lroot);

    if (!(/*RR<0||*/pos<RL))

       get+=ask(pos,RL,RR,Rroot);

    return get;

}

void insert(int pos,int L,int R,int inc,int root=1)

{

     segment_tree[root]+=inc;

     if (L==R) return;

     int LL=L,LR=(L+R)>>1,Lroot=root<<1;

     int RL=LR+1,RR=R,Rroot=Lroot|1;

     if (LL<=pos&&pos<=LR)

        insert(pos,LL,LR,inc,Lroot);

     if (RL<=pos&&pos<=RR)

        insert(pos,RL,RR,inc,Rroot);

}

 

void dfs_get_counter(int root,int father_of_root=0)

{

     counter[root]=ask(order[root],0,N-1);

     insert(order[root],0,N-1,+1);

     for (int i=0;i<children[root].size();i++)

         if (children[root][i]!=father_of_root)

            dfs_get_counter(children[root][i],root);

     insert(order[root],0,N-1,-1);

}

 

int main()

{

    freopen(“slowdown.in”,“r”,stdin);

    freopen(“slowdown.out”,“w”,stdout);

    scanf(“%d\n”,&N);

    for (int i=0;i<N-1;i++)

        scanf(“%d %d\n”,&A[i],&B[i]);

    for (int i=0;i<N;i++)

        scanf(“%d\n”,&P[i]);

   

    for (int i=0;i<N-1;i++)

    {

        children[A[i]].push_back(B[i]);

        children[B[i]].push_back(A[i]);

    }

    for (int i=0;i<N;i++)

        order[P[i]]=i;

    dfs_get_counter(1);

   

    for (int i=0;i<N;i++)

        printf(“%d\n”,counter[P[i]]);

   

    fclose(stdin);

    fclose(stdout);

    return 0;

}