JOI春合宿2013 Day2-3 Spy

解説みて解いた．問題が木だったらとりあえずEuler-Tourを使えないか考えるとよさそう．
二次元にして長方形を塗るという考え方は頭がいい．

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 2010, MAXM = 500000;
typedef pair<int,int> P;
int N,M;
vector<int> G[2][MAXN]; //部下の頂点番号
P vs[2][MAXN]; //その頂点がEuler Tour上で初めて現れる場所と最後に現れる場所
int boss[2];
int a[2*MAXN][2*MAXN];

void euler_tour(int g, int v, int *k){
	vs[g][v].first = vs[g][v].second = *k;
	(*k)++;
	for(int i = 0; i < G[g][v].size(); i++){
		int u = G[g][v][i];
		euler_tour(g, u, k);
		vs[g][v].second = *k;
		(*k)++;
	}
}
void read(){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++){
		int a, b;
		scanf("%d %d", &a, &b);
		if(a == 0)
			boss[0] = i;
		else
			G[0][a].push_back(i);
		if(b == 0)
			boss[1] = i;
		else
			G[1][b].push_back(i);
	}
	int k = 0;
	euler_tour(0,boss[0],&k);
	k = 0;
	euler_tour(1,boss[1],&k);
	for(int i=0;i<M;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		a[vs[0][x].first     ][vs[1][y].first     ]++;
		a[vs[0][x].second + 1][vs[1][y].first     ]--;
		a[vs[0][x].first     ][vs[1][y].second + 1]--;
		a[vs[0][x].second + 1][vs[1][y].second + 1]++;
	}
}
int main(){
	read();
	for(int i = 0; i <= 2*N; i++)
		for(int j = 1; j <= 2*N; j++)
			a[i][j]+=a[i][j-1];
	for(int i = 1; i <= 2*N; i++)
		for(int j = 0; j <= 2*N; j++)
			a[i][j]+=a[i-1][j];
	for(int i = 1; i <= N; i++){
		printf("%d\n", a[vs[0][i].first][vs[1][i].first]);
	}
}