推荐题目洛谷P3995 树链剖分题目背景树链剖分计算机术语指一种对树进行划分的算法它先通过轻重边剖分将树分为多条链保证每个点属于且只属于一条链然后再通过数据结构树状数组、SBT、SPLAY、线段树等来维护每一条链。(摘自百度百科)题目描述大宁最近在研究树链剖分。他发现树链剖分的时间复杂度主要由轻重链的划分方式保证最常见的剖分方式是按照子树大小剖分。如图摘自百度百科黑边为重链长度任意白边为轻链长度全部为1。注意下图 1-2, 1-3 为不同轻链。其中对于每个节点其在重链上的儿子叫做重儿子且只有唯一一个而叶子节点没有重儿子。例如对于图上 1 号点重儿子是 4 号点。显然对于不同剖分方式同一组查询访问的链的数量不同。现在给定一棵根为 1 号节点的有根树和若干询问操作每次询问访问从u uu到v vv上面的所有轻重链一次。例如在上图的剖分方式中查询 3 到 8 一共访问了 3 条轻链 1-3重链 1-4轻链 4-8查询 3 到 11 一共访问了 3 条轻链 1-3轻链 1-2重链 2-11。大宁请你给出一种剖分方案使所有询问操作总共访问的轻重链总条数最小由于可能有许多合法方案请任意输出一种我们提供Special Judge检验你的方案的正确性。设你的剖分方式的查询链数为x xxstd 答案的查询数为x 0 x_0x0评分参数为a aa。你得到的分数是10 1010分 当x ≤ x 0 x\leq x_0x≤x0。8 88分 当0 ( x − x 0 ) ≤ a 0(x-x_0)\leq a0(x−x0)≤a。7 77分 当a ( x − x 0 ) ≤ 2 × a a(x-x0)\leq 2\times aa(x−x0)≤2×a。6 66分 当2 × a ( x − x 0 ) ≤ 3 × a 2\times a(x-x0)\leq 3\times a2×a(x−x0)≤3×a。1 11分 输出了合法的方案。a ⌊ q 300 ⌋ a\lfloor\frac{q}{300}\rfloora⌊300q⌋,q qq为询问总数。我们提供了Div\_Checker.exe来检验你的答案。把它放到div.in,div.out同文件夹下运行其中div.in是输入数据的文件形式,div.out是你的程序在该输入下的输出。如果你的div.out答案合法它会返回Your answer is XXX.XXX是你的剖分方式在该输入数据下的查询次数否则返回Wrong Outdata.注意: 在正式提交的时候不能使用文件输入输出。输入格式第一行有两个正整数n nn和q qq表示该树的节点数n nn和查询次数q qq。接下来n − 1 n-1n−1行各有两个正整数u uuv vv表示u uu和v vv之间有一条边。接下来q qq行为q qq个询问为U UUV VV表示有一次从U UU到V VV的询问。输出格式一共n nn行对于i ii号节点如果它不是叶子节点那么输出它在你的剖分方案里的重儿子否则输出 0。输入输出样例 #1输入 #114 7 1 4 4 10 4 9 4 8 9 13 13 14 3 1 7 3 2 1 2 6 6 12 11 6 5 2 11 3 7 8 2 8 11 1 8 14 5 7 9 14输出 #12 6 7 8 0 11 0 0 13 0 0 0 14 0说明/提示样例即为上图但图上的剖分方式对于此处的查询并非最优。对于20 % 20\%20%的数据n , q 10 n,q10n,q10对于60 % 60\%60%的数据n , q 1000 n,q1000n,q1000对于100 % 100\%100%的数据1 n 100000 1n1000001n100000,1 q 200000 1q2000001q200000,保证给出的是一棵合法的树。Div_Checker下载如果对Checker的使用方式不太理解请参照下面的图片图中数据为样例。一个合法方案的输出。不合法方案的输出。upd 2022.8.26 \text{upd 2022.8.26}upd 2022.8.26新增加一组 Hack 数据。
推荐题目洛谷P3995 树链剖分题目背景树链剖分计算机术语指一种对树进行划分的算法它先通过轻重边剖分将树分为多条链保证每个点属于且只属于一条链然后再通过数据结构树状数组、SBT、SPLAY、线段树等来维护每一条链。(摘自百度百科)题目描述大宁最近在研究树链剖分。他发现树链剖分的时间复杂度主要由轻重链的划分方式保证最常见的剖分方式是按照子树大小剖分。如图摘自百度百科黑边为重链长度任意白边为轻链长度全部为1。注意下图 1-2, 1-3 为不同轻链。其中对于每个节点其在重链上的儿子叫做重儿子且只有唯一一个而叶子节点没有重儿子。例如对于图上 1 号点重儿子是 4 号点。显然对于不同剖分方式同一组查询访问的链的数量不同。现在给定一棵根为 1 号节点的有根树和若干询问操作每次询问访问从u uu到v vv上面的所有轻重链一次。例如在上图的剖分方式中查询 3 到 8 一共访问了 3 条轻链 1-3重链 1-4轻链 4-8查询 3 到 11 一共访问了 3 条轻链 1-3轻链 1-2重链 2-11。大宁请你给出一种剖分方案使所有询问操作总共访问的轻重链总条数最小由于可能有许多合法方案请任意输出一种我们提供Special Judge检验你的方案的正确性。设你的剖分方式的查询链数为x xxstd 答案的查询数为x 0 x_0x0评分参数为a aa。你得到的分数是10 1010分 当x ≤ x 0 x\leq x_0x≤x0。8 88分 当0 ( x − x 0 ) ≤ a 0(x-x_0)\leq a0(x−x0)≤a。7 77分 当a ( x − x 0 ) ≤ 2 × a a(x-x0)\leq 2\times aa(x−x0)≤2×a。6 66分 当2 × a ( x − x 0 ) ≤ 3 × a 2\times a(x-x0)\leq 3\times a2×a(x−x0)≤3×a。1 11分 输出了合法的方案。a ⌊ q 300 ⌋ a\lfloor\frac{q}{300}\rfloora⌊300q⌋,q qq为询问总数。我们提供了Div\_Checker.exe来检验你的答案。把它放到div.in,div.out同文件夹下运行其中div.in是输入数据的文件形式,div.out是你的程序在该输入下的输出。如果你的div.out答案合法它会返回Your answer is XXX.XXX是你的剖分方式在该输入数据下的查询次数否则返回Wrong Outdata.注意: 在正式提交的时候不能使用文件输入输出。输入格式第一行有两个正整数n nn和q qq表示该树的节点数n nn和查询次数q qq。接下来n − 1 n-1n−1行各有两个正整数u uuv vv表示u uu和v vv之间有一条边。接下来q qq行为q qq个询问为U UUV VV表示有一次从U UU到V VV的询问。输出格式一共n nn行对于i ii号节点如果它不是叶子节点那么输出它在你的剖分方案里的重儿子否则输出 0。输入输出样例 #1输入 #114 7 1 4 4 10 4 9 4 8 9 13 13 14 3 1 7 3 2 1 2 6 6 12 11 6 5 2 11 3 7 8 2 8 11 1 8 14 5 7 9 14输出 #12 6 7 8 0 11 0 0 13 0 0 0 14 0说明/提示样例即为上图但图上的剖分方式对于此处的查询并非最优。对于20 % 20\%20%的数据n , q 10 n,q10n,q10对于60 % 60\%60%的数据n , q 1000 n,q1000n,q1000对于100 % 100\%100%的数据1 n 100000 1n1000001n100000,1 q 200000 1q2000001q200000,保证给出的是一棵合法的树。Div_Checker下载如果对Checker的使用方式不太理解请参照下面的图片图中数据为样例。一个合法方案的输出。不合法方案的输出。upd 2022.8.26 \text{upd 2022.8.26}upd 2022.8.26新增加一组 Hack 数据。
