1782: [Usaco2010 Feb]slowdown 慢慢游

1782: [Usaco2010 Feb]slowdown 慢慢游

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 570  Solved: 346
[Submit][Status][Discuss]

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

HINT

 

Source

Gold

题解：其实就是求以1为根节点的树上从树根到某一点的链上比自己权值小的点的个数

这样子经典的问题直接树转数组搞定= =，省选前刷水感觉棒棒哒

 /**************************************************************

     Problem:

     User: HansBug

     Language: Pascal

     Result: Accepted

     Time: ms

     Memory: kb

 ****************************************************************/

 type

     point=^node;

     node=record

                g:longint;

                next:point;

     end;

 var

    i,j,k,l,m,n,t:longint;

    a:array[..] of point;

    b,c:array[..,..] of longint;

    d,e:array[..] of longint;

 procedure swap(var x,y:longint);

           var z:longint;

           begin

                z:=x;x:=y;y:=z;

           end;

 procedure sort(l,r:longint);

           var i,j,x,y:longint;

           begin

                i:=l;j:=r;x:=c[(l+r) div ,];

                repeat

                      while c[i,]<x do inc(i);

                      while c[j,]>x do dec(j);

                      if i<=j then

                         begin

                              swap(c[i,],c[j,]);

                              swap(c[i,],c[j,]);

                              inc(i);dec(j);

                         end;

                until i>j;

                if i<r then sort(i,r);

                if l<j then sort(l,j);

           end;

 procedure edg(x,y:longint);

           var p:point;

           begin

                new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;

           end;

 function sum(x:longint):longint;

          begin

               sum:=;

               while x> do

                     begin

                          inc(sum,d[x]);

                          dec(x,x and (-x));

                     end;

          end;

 procedure add(x,y:longint);

           begin

                if x= then exit;

                while x<=n do

                      begin

                           inc(d[x],y);

                           inc(x,x and (-x));

                      end;

           end;

 procedure dfs(y,x:longint);

           var p:point;

           begin

                add(x,);

                e[x]:=sum(x-);p:=a[x];

                while p<>nil do

                      begin

                           if p^.g<>y then dfs(x,p^.g);

                           p:=p^.next;

                      end;

                add(x,-);

           end;

 begin

      readln(n);t:=;

      for i:= to n- do readln(b[i,],b[i,]);

      for i:= to n do

          begin

               c[i,]:=i;

               readln(c[i,]);

          end;

      sort(,n);

      for i:= to n- do

          begin

               b[i,]:=c[b[i,],];

               b[i,]:=c[b[i,],];

               edg(b[i,],b[i,]);

               edg(b[i,],b[i,]);

          end;

      t:=c[t,];

      fillchar(d,sizeof(d),);

      dfs(,t);

      for i:= to n do writeln(e[i]);

      readln;

 end.