78 lines
1.9 KiB
C++
78 lines
1.9 KiB
C++
#include <algorithm>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
#include <vector>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
const int kMaxn = 2e5 + 10;
|
|
struct DataType {
|
|
int r, y;
|
|
int uid, dfn, boundary;
|
|
} val[kMaxn], tmp[kMaxn];
|
|
vector<int> G[kMaxn];
|
|
int n, dfn_cnt, res[kMaxn];
|
|
void PreWork(int u, int fa) {
|
|
val[u].dfn = ++dfn_cnt;
|
|
for (int v : G[u]) {
|
|
if (v == fa) continue;
|
|
PreWork(v, u);
|
|
}
|
|
val[u].boundary = dfn_cnt;
|
|
}
|
|
class BSTType {
|
|
LL data[kMaxn];
|
|
int len = 0;
|
|
|
|
public:
|
|
void Init(int n) { len = n; }
|
|
void Modify(int p, int v) {
|
|
for (; p <= len; p += p & (-p)) data[p] += v;
|
|
}
|
|
LL Query(int p) {
|
|
LL res = 0;
|
|
for (; p > 0; p -= p & (-p)) res += data[p];
|
|
return res;
|
|
}
|
|
} BST;
|
|
void CDQ(int L, int R) {
|
|
if (L == R) return;
|
|
int M = (L + R) >> 1;
|
|
CDQ(L, M);
|
|
CDQ(M + 1, R);
|
|
sort(val + L, val + M + 1,
|
|
[](const DataType &A, const DataType &B) { return A.r < B.r; });
|
|
sort(val + M + 1, val + R + 1,
|
|
[](const DataType &A, const DataType &B) { return A.r < B.r; });
|
|
int pl = L, pr = M + 1;
|
|
while (pr <= R) {
|
|
while (pl <= M && val[pl].r <= val[pr].r) BST.Modify(val[pl++].dfn, 1);
|
|
res[val[pr].uid] += BST.Query(val[pr].boundary) - BST.Query(val[pr].dfn);
|
|
pr++;
|
|
}
|
|
for (int i = L; i < pl; i++) BST.Modify(val[i].dfn, -1);
|
|
}
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif
|
|
scanf("%d", &n);
|
|
for (int i = 1; i <= n - 1; i++) {
|
|
int u, v;
|
|
scanf("%d%d", &u, &v);
|
|
G[u].push_back(v);
|
|
G[v].push_back(u);
|
|
}
|
|
for (int i = 1; i <= n; i++) {
|
|
scanf("%d%d", &val[i].r, &val[i].y);
|
|
val[i].uid = i;
|
|
}
|
|
PreWork(1, 0);
|
|
BST.Init(n);
|
|
sort(val + 1, val + 1 + n, [](const DataType &A, const DataType &B) {
|
|
return A.y != B.y ? A.y < B.y : (A.r != B.r ? A.r < B.r : A.dfn > B.dfn);
|
|
});
|
|
CDQ(1, n);
|
|
for (int i = 1; i <= n; i++)
|
|
if (res[i] != 0) printf("%d\n", res[i]);
|
|
return 0;
|
|
} |