{"problem":{"name":"「DTOI-2」星之河","description":{"content":"星之统治者有一个星盘，其可以被抽象为一棵根节点为 $1$ 的树。树上每个节点 $i$ 有一颗红星、一颗蓝星，亮度分别记为 $\\text{Red}_i,\\text{Blue}_i$。 现在，星之统治者想要知道，对于每个节点 $x$，其子树内（不包括该节点）有多少节点满足：其红星亮度小于等于 $x$ 的红星亮度，且其蓝星亮度小于等于 $x$ 的蓝星亮度。 你需要按编号顺序依次输出每个节点的答案。为","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":65536},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8575"},"statements":[{"statement_type":"Markdown","content":"星之统治者有一个星盘，其可以被抽象为一棵根节点为 $1$ 的树。树上每个节点 $i$ 有一颗红星、一颗蓝星，亮度分别记为 $\\text{Red}_i,\\text{Blue}_i$。\n\n现在，星之统治者想要知道，对于每个节点 $x$，其子树内（不包括该节点）有多少节点满足：其红星亮度小于等于 $x$ 的红星亮度，且其蓝星亮度小于等于 $x$ 的蓝星亮度。\n\n你需要按编号顺序依次输出每个节点的答案。为减少输出量，**如果答案为 $0$ 则不必输出。**\n\n## Input\n\n第一行一个整数表示 $n$。\n\n接下来 $n-1$ 行每行两个正整数 $u,v$，表示存在 $(u,v)$ 这条树边。\n\n接下来 $n$ 行每行两个整数分别表示 $\\text{Red}_i, \\text{Blue}_i$。\n\n## Output\n\n每个答案非 $0$ 的节点一行，每行一个整数表示答案。\n\n[samples]\n\n## Background\n\n> 星稀河影转，霜重月华孤。\n\n## Note\n\n### 样例解释\n\n对于节点 $1$，小于等于他的子节点有 $6,7,8,9,10$，因此输出 $5$。  \n对于节点 $4$，小于等于他的子节点有 $6$，因此输出 $1$。  \n对于节点 $5 $ 至 $10$，没有小于等于他的子节点，因此不输出。\n\n### 数据范围\n\n| $\\textbf{Subtask}$| $n\\le$ | 特殊性质 | 总分数 |\n| :-----------: | :-----------: | :-----------: | :-----------: |\n| $1$ | $1000$ | 无 | $10$ |\n| $2$ | $5\\times 10^4$ | 无 | $20$ ||\n| $3$ | $10^5$ | $-200\\le \\text{Red}_i, \\text{Blue}_i \\le 200$ | $20$ |\n| $4$ | $2\\times 10^5$ | 树的形态是链 | $20$ |\n| $5$ | $2\\times 10^5$ | 无 | $30$ |\n\n对于所有数据，保证 $n \\le 2\\times 10^5$，$-10^9 \\le \\text{Red}_i, \\text{Blue}_i \\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8575","tags":["cdq 分治"],"sample_group":[["10\n2 1\n3 1\n4 3\n5 1\n6 4\n7 2\n8 2\n9 4\n10 3\n3 1\n2 4\n-3 3\n4 -2\n-2 3\n-3 -6\n-5 -1\n-4 -7\n-5 -1\n-7 -7","5\n2\n3\n1"]],"created_at":"2026-03-03 11:09:25"}}