#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <bitset>
#define Tpair pair <int, int>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e9 + 1;
int n, m, i, T, par[3][2005], child[3][2005], pos[3][2005], cnt[3], p[3], root[3], s[3],
ans[2005], pos2[3][2005], dem;
bitset <60> sum[3][2005], bit[3], res[3][2005];
vector <int> v[3][2005];
void Dfs (int x, int pre, int idx)
{
par[idx][x] = pre;
child[idx][x] = 1;
pos[idx][x] = ++cnt[idx];
pos2[idx][cnt[idx]] = x;
for (int j : v[idx][x])
if (!par[idx][j])
{
Dfs (j, x, idx);
child[idx][x] += child[idx][j];
}
}
void Init()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
cin >> p[1] >> p[2];
if (p[1] != 0) v[1][p[1]].push_back (i);
if (p[2] != 0) v[2][p[2]].push_back (i);
if (p[1] == 0) root[1] = i;
if (p[2] == 0) root[2] = i;
}
Dfs (root[1], root[1], 1);
Dfs (root[2], root[2], 2);
//for (int i = 1; i <= n; ++i) cout << i << " " << par[1][i] << " " << child[1][i] << " " << pos[1][i] << '\n';
//for (int i = 1; i <= n; ++i) cout << i << " " << par[2][i] << " " << child[2][i] << " " << pos[2][i] << '\n';
}
void Reset()
{
for (int i = 1; i <= n; ++i)
{
bit[1] ^= sum[1][i];
bit[2] ^= sum[2][i];
res[1][i] = bit[1];
res[2][i] = bit[2];
//cout << sum[1][i] << endl << sum[2][i] << endl;
}
for (int i = 1; i <= n; ++i) ans[i] = (res[1][pos[1][i]] & res[2][pos[2][i]]).count();
dem = 0;
for (int i = 1; i <= n; ++i)
{
res[1][i].reset();
res[2][i].reset();
sum[1][i].reset();
sum[2][i].reset();
}
bit[1].reset(); bit[2].reset();
}
void Solve()
{
for (int i = 1; i <= m; ++i)
{
cin >> s[1] >> s[2];
sum[1][pos[1][s[1]]][dem] = 1;
sum[2][pos[2][s[2]]][dem] = 1;
sum[1][pos[1][s[1]] + child[1][s[1]]][dem] = 1;
sum[2][pos[2][s[2]] + child[2][s[2]]][dem] = 1;
++dem;
if (i % 60 == 0) Reset();
}
Reset();
for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen ("spy.inp", "r", stdin);
//freopen ("spy.out", "w", stdout);
Init();
Solve();
}
// Date 15 Month 11 Year 2017
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
2512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
336 ms |
2672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
