{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYankovich在一个名为POI(无限在线派对)的公司担任软件工程师,正如其名称所示,这是一家推广在线派对的公司。为了测试系统,一些员工举办了派对,并只邀请公司员工参加,但有一些限制条件。\u003c/p\u003e\u003cp\u003e公司员工构成一个分层结构,每个员工都有一个直接经理(除了公司所有者),并且没有循环关系。由于公司的晋升流程,员工的年龄不会大于其直接经理的年龄。\u003c/p\u003e\u003cp\u003e这些初始派对的工作方式如下:\u003c/p\u003e\u003cul\u003e \u003cli\u003e 每个派对 $$$j$$$ 都有一个所有者 $$$O_j$$$ 和一个年龄范围,从 $$$L_j$$$ 到 $$$R_j$$$ 。\u003c/li\u003e\u003cli\u003e 要被邀请参加派对,员工的年龄需要在派对的年龄范围 $$$[L_j, R_j]$$$ 内。保证每个派对的所有者的年龄都在他们派对的年龄范围内。\u003c/li\u003e\u003cli\u003e 除了年龄限制,要被邀请参加派对,员工必须直接与另一位将被邀请的员工一起工作(作为直接经理或直接下属),除了派对的所有者。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eYankovich负责计算用户参与的派对数据的应用程序。作为初始任务,他必须计算员工被邀请参加了多少个派对。由于他已经迟交了他的第一个任务,帮助他计算这些初始派对的信息。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含两个整数 $$$N, M$$$ $$$(1 \\le N, M \\le 10^5)$$$,分别表示员工数量和初始派对数量。\u003c/p\u003e\u003cp\u003e接下来的 $$$N$$$ 行包含员工数据。在这些行中,第 $$$i$$$ 行包含两个整数 $$$A_i, B_i$$$ $$$(1 \\le A_i ≤ 10^5, 1 \\le B_i \\le N)$$$,表示第 $$$i$$$ 个员工的年龄和他的直接经理(员工编号从1到 $$$N$$$,公司所有者的编号为1,他是唯一一个有 $$$B_i \u003d i$$$ 的员工)。保证 $$$A_i \\le A_{B_i}$$$。\u003c/p\u003e\u003cp\u003e接下来的 $$$M$$$ 行定义了初始派对。在这些行中,第 $$$j$$$ 行包含三个整数 $$$O_j, L_j, R_j$$$ $$$(1 \\le L_j \\le A_{O_j} \\le R_j \\le 10^5)$$$,表示这个派对的所有者和其年龄范围。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一行,包含 $$$N$$$ 个整数(用单个空格分隔)。其中第 $$$i$$$ 个数字应该是员工编号为 $$$i$$$ 的员工被邀请参加的派对数量。\u003c/p\u003e"}},{"title":"示例1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10 3\n8 1\n3 5\n5 1\n2 3\n4 1\n3 3\n1 2\n7 1\n2 2\n3 2\n3 5 9\n5 3 8\n3 2 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 3 1 1 2 0 2 0 1 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}