no_2.cpp

我们acm的题目

#include <iostream> 
#include <cstring> 
using namespace std;

int a, b, i, k, l, n;

int d[5001], sum[1001], npos[1001], pos[1001], ts[5001];

//Disjoint set with operation of PULL. typedef struct { int t[5001], father[5001];
typedef struct
{	
	int t[5001], father[5001];
    void pull(int p) 
	{ 
		if (!father[p]) 
             return; 
         pull(father[p]); 
         father[father[p]] = p; 
         father[p] = 0; 
	}

    void fill(int p, int q)
	{ 
		if (t[p] <= q) return; 
        t[p] = q; 
        if (father[p]) 
	       fill(father[p], q + 1);
	}

    void calc(int p) 
	{ 
	if (!father[p] || d[p]) 
      return; 
	calc(father[p]); 
     d[p] = d[father[p]] + 1; 
	}

   void calc1(int p) 
   {
	if (ts[p]) return; 
	if (!father[p]) 
	{
		ts[p] = t[p]; 
	     return;
	} 
	calc1(father[p]);
	if (ts[father[p]] <t[p]) 
		ts[p] = ts[father[p]]; 
	else ts[p] = t[p]; 
   }

   void move(int p, int q) 
   { 
	d[pos[p]] = 1;
	if (!father[pos[p]]) return; 
	if (ts[father[pos[p]]] > q && !d[father[pos[p]]])
	{ 
		pos[p] = father[pos[p]];
	    move(p, q + 1); 
	} 
   }

  void setnull_father()
  { 
	memset(father, 0, sizeof(father)); 
  }

   void fillt() 
   { 
	for (i = 1; i <= n; i ++) 
		t[i] = 2000000000;
   }

} disjoint_set;

disjoint_set set;

void qsort(int l, int r) 
{ int i, j, x, y;
 i = l; j = r;
 x = npos[(i + j) >> 1];
 while (i <= j)
 {
	 while (d[npos[i]] < d[x])
		 i ++; 
	 while (d[x] < d[npos[j]]) 
		 j --; 
	 if (i <=j) 
	 {
		 y = npos[i]; 
		 npos[i] = npos[j]; 
		 npos[j] = y;
		 i ++; 
		 j --;
 }
 } 
 if (l < j) 
	 qsort(l, j);
 if (i < r) qsort(i, r);
 }

void work() 
{ 
	cin >> a;
	set.pull(a);

    memset(d, 0, sizeof(d)); 
	for (i = 1; i <= k; i ++) set.calc(pos[i]);
     memcpy(npos, pos, sizeof(pos)); 
	qsort(1, k); set.fillt();

for (i = 1; i <= k; i ++) 
   set.fill(npos[i], 0);

   memset(ts, 0, sizeof(ts)); 
for (i = 1; i <= k; i ++) 
   set.calc1(pos[i]);

   memset(d, 0, sizeof(d)); 
for (i = 1; i <= k; i ++) 
    set.move(i, 0);
for (i = 1; i <= k; i ++) 
    if (pos[i] == a)
		sum[i] ++;

}

int main() 
{ 
	while (cin >> n) 
	{ memset(sum, 0, sizeof(sum));

   set.setnull_father(); 
   for (i = 1; i < n; i ++) 
   { 
	   cin >> a >> b; 
	   set.pull(a); 
	   set.father[a] = b; 
   } 
   cin >> k;
   for (i = 1; i <= k; i ++) 
	   cin >> pos[i];

cin >> l; 
for (int time = 1; time <= l; time ++)
 work();

for (i = 1; i <= k; i ++)
 cout << pos[i] << " " << sum[i] << endl;
 } 
	return 0; 
}