{"problem":{"name":"『GROI-R1』 古朴而优雅","description":{"content":"杉虽然年事已高，但是还是保持与时俱进。他学习了深度优先遍历算法，觉得这种新潮的东西在一所古朴而优雅的学院里会很受欢迎。所以，他找到了在走廊里晃荡的寒，向他提出了一个问题： 「我们知道，对一棵树进行深度优先遍历可以用下面的伪代码很好地解决。」 $$ \\begin{array}{l} \\text{DFS-TREE}(u)\\\\ \\begin{array}{ll} 1 & p\\gets p+1\\\\ 2","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8974"},"statements":[{"statement_type":"Markdown","content":"杉虽然年事已高，但是还是保持与时俱进。他学习了深度优先遍历算法，觉得这种新潮的东西在一所古朴而优雅的学院里会很受欢迎。所以，他找到了在走廊里晃荡的寒，向他提出了一个问题：\n\n「我们知道，对一棵树进行深度优先遍历可以用下面的伪代码很好地解决。」\n\n$$\n\\begin{array}{l}\n\\text{DFS-TREE}(u)\\\\\n\\begin{array}{ll}\n1 & p\\gets p+1\\\\\n2 & t_p\\gets u\\\\\n3 & vis_u\\gets 1\\\\\n4 & \\textbf{for }\\text{each edge }(u,v)\\in E \\\\\n5 & \\qquad \\textbf{if }vis_v=0\\\\\n6 & \\qquad \\qquad \\text{DFS-TREE}(v)\\\\\n7 & p\\gets p+1\\\\\n8 & t_p\\gets u\\\\\n\\end{array}\n\\end{array}\n$$\n\n起初，所有变量或数组的值均为 $0$。\n\n「我们把调用 $\\text{DFS-TREE}(1)$ 在遍历过程中得到的数组 $t$ 称为这棵树的**遍历顺序**。」\n\n「你看这段代码的第 $4$ 行，这句话**遍历每一条边的顺序是不固定的**。」\n\n寒素来最讨厌不确定的东西，可是碍于院长的颜面，还是继续听下去。\n\n「你能数出这段代码**会生成多少种不同的遍历顺序**吗？」\n\n寒发现他曾经做过这个题，很快地报出了解法。本以为就结束了，可是杉继续说：\n\n「如果我**在树上增加一条边**，你还会做吗？」\n\n寒发现他的那点水平完全不够了，于是他去请教玘。玘却认为这道题目依然很简单，他告诉了寒这道题的做法。可是寒找不到杉了。\n\n这个世界到底怎么了呢？\n\n## Input\n\n第一行，两个整数 $n$ 和 $q$，表示树上有 $n$ 个结点，编号为 $1\\sim n$，有 $q$ 次询问。\n\n接下来 $n-1$ 行，每行两个整数 $u,v$，描述这棵树上的一条边。\n\n接下来 $q$ 行，每行两个整数 $x,y$，表示在树上添加连接 $x$ 和 $y$ 的一条边，询问有多少种可能的遍历顺序。注意：每次询问是**互相独立的**，也就是说，上一次询问添加的边不会保留到下一次询问。\n\n## Output\n\n共 $q$ 行，每行一个整数表示这次询问的答案对 $10^9+7$ 取模后得到的值。\n\n[samples]\n\n## Background\n\n会馆内忽地安静了下来。\n\n「敝姓言，名杉。」\n\n他的声音沉稳而凝重，略带沙哑，却不失力度，极具穿透力。每个字都重重地打在耳畔，渗进头脑里，让人想不认真听都难。\n\n「这所学院的院长。」\n\n## Note\n\n**样例解释**\n\n对于第一次询问可以得到如图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ojeiswc8.png)\n\n能得到的遍历顺序有：\n\n- $\\{1,2,3,3,2,4,4,1\\}$\n- $\\{1,4,4,2,3,3,2,1\\}$\n- $\\{1,3,2,2,3,4,4,1\\}$\n- $\\{1,4,4,3,2,2,3,1\\}$\n\n对于第二次询问可以得到如图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/6dut5s4r.png)\n\n能得到的遍历顺序有：\n\n- $\\{1,2,2,3,3,4,4,1\\}$\n- $\\{1,2,2,4,4,3,3,1\\}$\n- $\\{1,3,3,2,2,4,4,1\\}$\n- $\\{1,3,3,4,4,2,2,1\\}$\n- $\\{1,4,4,2,2,3,3,1\\}$\n- $\\{1,4,4,3,3,2,2,1\\}$\n\n**数据范围**\n\n**本题采用捆绑测试。**\n\n| 测试点编号 | 数据范围 | 特殊性质 | 分值 |\n| :-----------: | :-----------: | :-----------: | :-----------: |\n| $\\text{Subtask1}$ | $n,q\\le8$ |  | $5$ |\n| $\\text{Subtask2}$ | $n,q\\le20$ |  | $10$ |\n| $\\text{Subtask3}$ | $n,q\\le500$ |  | $10$ |\n| $\\text{Subtask4}$ | $n,q\\le3000$ |  | $15$ |\n| $\\text{Subtask5}$ | $n,q\\le2\\times10^5$ | $\\text{A}$ | $15$ |\n| $\\text{Subtask6}$ | $n,q\\le2\\times10^5$ | $\\text{B}$ | $10$ |\n| $\\text{Subtask7}$ | $n,q\\le2\\times10^5$ |  | $35$ |\n\n特殊性质 $\\text{A}$：保证每一次询问的边 $(x,y)\\in E$。\n\n特殊性质 $\\text{B}$：保证树退化成一条链。\n\n对于 $100\\%$ 的数据保证 $1\\le n,q\\le2\\times10^5$，$1\\le u,v,x,y\\le n$，$x\\ne y$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8974","tags":["数学","图论","O2优化","最近公共祖先 LCA","基环树"],"sample_group":[["4 2\n1 2\n1 3\n1 4\n2 3\n1 4","4\n6"]],"created_at":"2026-03-03 11:09:25"}}