洛谷P2982 [USACO10FEB]慢下来Slowing down(线段树 DFS序区间增减单点查询)

题目描述

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.

每天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会放慢自己的速度，防止打扰他的朋友。

FJ想要知道奶牛们总共要放慢多少次速度。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

代码：

 1 #include<cstdio>
 2 #include<cctype>
 3 using namespace std;
 4 const int N=100005;
 5 
 6 int n,ENum,cnt,H[N<<1],Sum[N<<2],Dfn[N],Size[N];
 7 struct Edge
 8 {
 9     int to,nxt;
10 }e[N<<1];
11 
12 void read(int &now)
13 {
14     now=0;char c=getchar();
15     for(;!isdigit(c);c=getchar());
16     for(;isdigit(c);c=getchar())
17       now=(now<<3)+(now<<1)+c-'0';
18 }
19 
20 void AddEdge(int u,int v)
21 {
22     e[++ENum].to = v;
23     e[ENum].nxt = H[u];
24     H[u] = ENum;
25 }
26 
27 void DFS(int x)
28 {
29     Size[x]=1;//根的子树的大小(包括自己) 
30     Dfn[x]=++cnt;//Dfn[i]:i在dfs序中的下标 
31     for(int i=H[x];i;i=e[i].nxt)
32     {
33         int to=e[i].to;
34         if(Dfn[to]) continue;
35         DFS(to);
36         Size[x]+=Size[to];
37     }
38 }
39 
40 void PushUp(int rt)
41 {
42     Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];
43 }
44 void PushDown(int rt)
45 {
46     if(!Sum[rt]) return;
47     Sum[rt<<1]+=Sum[rt];
48     Sum[rt<<1|1]+=Sum[rt];
49     Sum[rt]=0;
50 }
51 void ModifySum(int l,int r,int rt,int L,int R)
52 {
53     if(L<=l && r<=R)
54     {
55         ++Sum[rt];//区间修改时 针对本题 懒标记+1 
56         return;
57     }
58     PushDown(rt);
59     int m=(l+r)>>1;
60     if(L<=m) ModifySum(l,m,rt<<1,L,R);
61     if(m<R) ModifySum(m+1,r,rt<<1|1,L,R);
62     //PushUp(rt); 不需要进行PushUp!! 
63 }
64 int QuerySum(int l,int r,int rt,int p)
65 {
66     if(l==r) return Sum[rt];
67     PushDown(rt);
68     int m=(l+r)>>1,res=0;
69     if(p<=m) res+=QuerySum(l,m,rt<<1,p);
70     else res+=QuerySum(m+1,r,rt<<1|1,p);
71     return res;
72 }
73 
74 int main()
75 {
76     read(n);
77     for(int i=1;i<n;i++)
78     {
79         int a,b;
80         read(a);read(b);
81         AddEdge(a,b);
82         AddEdge(b,a);
83     }
84     DFS(1);
85 //    for(int i=1;i<=n;i++)
86 //      printf("%d:dfn:%d  size:%d
",i,Dfn[i],Size[i]);
87     for(int i=1;i<=n;i++)
88     {
89         int a;
90         read(a);
91         printf("%d
",QuerySum(1,n,1,Dfn[a]));//先经过后更改 
92         ModifySum(1,n,1,Dfn[a],Dfn[a]+Size[a]-1);//单点查询 区间修改 
93     }
94     return 0;
95 }