「DTOI-2」星之河

Luogu

IDLGP8575

Time1000ms

Memory64MB

DifficultyP6

cdq 分治

星之统治者有一个星盘，其可以被抽象为一棵根节点为 $1$ 的树。树上每个节点 $i$ 有一颗红星、一颗蓝星，亮度分别记为 $\text{Red}_i,\text{Blue}_i$。现在，星之统治者想要知道，对于每个节点 $x$，其子树内（不包括该节点）有多少节点满足：其红星亮度小于等于 $x$ 的红星亮度，且其蓝星亮度小于等于 $x$ 的蓝星亮度。你需要按编号顺序依次输出每个节点的答案。为减少输出量，**如果答案为 $0$ 则不必输出。** ## Input 第一行一个整数表示 $n$。接下来 $n-1$ 行每行两个正整数 $u,v$，表示存在 $(u,v)$ 这条树边。接下来 $n$ 行每行两个整数分别表示 $\text{Red}_i, \text{Blue}_i$。 ## Output 每个答案非 $0$ 的节点一行，每行一个整数表示答案。 [samples] ## Background > 星稀河影转，霜重月华孤。 ## Note ### 样例解释对于节点 $1$，小于等于他的子节点有 $6,7,8,9,10$，因此输出 $5$。对于节点 $4$，小于等于他的子节点有 $6$，因此输出 $1$。对于节点 $5 $ 至 $10$，没有小于等于他的子节点，因此不输出。 ### 数据范围 | $\textbf{Subtask}$| $n\le$ | 特殊性质 | 总分数 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $1000$ | 无 | $10$ | | $2$ | $5\times 10^4$ | 无 | $20$ || | $3$ | $10^5$ | $-200\le \text{Red}_i, \text{Blue}_i \le 200$ | $20$ | | $4$ | $2\times 10^5$ | 树的形态是链 | $20$ | | $5$ | $2\times 10^5$ | 无 | $30$ | 对于所有数据，保证 $n \le 2\times 10^5$，$-10^9 \le \text{Red}_i, \text{Blue}_i \le 10^9$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "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你需要按编号顺序依次输出每个节点的答案。为...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments