{"problem":{"name":"[北大集训 2021] 小明的树","description":{"content":"小明有一棵以 $1$ 为根的 $n$ 个节点的树，树上每一个非根节点上有一盏灯，他有一个 $2 \\thicksim n$ 的排列 $a_1,a_2,\\dots,a_{n-1}$。他还有一个计数器，初始为 $0$。 他会按照排列依次点亮这 $n-1$ 盏灯，每进行一次点灯操作后，他会检查整个树是否是美丽的，如果是美丽的，计数器会加上此时点灯的节点形成的连通块的个数。 $n-1$ 次点灯后计数器的","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8990"},"statements":[{"statement_type":"Markdown","content":"小明有一棵以 $1$ 为根的 $n$ 个节点的树，树上每一个非根节点上有一盏灯，他有一个 $2 \\thicksim n$ 的排列 $a_1,a_2,\\dots,a_{n-1}$。他还有一个计数器，初始为 $0$。\n\n他会按照排列依次点亮这 $n-1$ 盏灯，每进行一次点灯操作后，他会检查整个树是否是美丽的，如果是美丽的，计数器会加上此时点灯的节点形成的连通块的个数。\n\n$n-1$ 次点灯后计数器的值，记为这棵树的答案。\n\t\t\t\t\n\n一个树是美丽的当前仅当对于每一个被点亮的节点，这个节点子树内的节点都是点亮的。\n\n小明认为这个问题太简单了，他觉得应该让树动起来。\n\n在初始查询后，他会删掉树中一条边并加上一条边，保证修改后还是一棵树，他想知道每一次修改后将计数器清零后重新点灯并计数，这棵树的答案是多少。\n\n## Input\n\n第一行两个数 $n,m$ ,表示树的节点数为 $n$，有 $m$ 次修改。\n\n接下来 $n-1$ 行，每行 $2$ 个数，表示一条边。\n\n下一行 $n-1$ 个数 $a_i$，表示一个 $2 \\thicksim n$ 的排列。\n\n接下来 $m$ 行每行四个数，$x_1,y_1,x_2,y_2$ 表示断开 $x_1,y_1$ 间的边并连接 $x_2,y_2$，保证数据合法。\n\n## Output\n\n共 $m+1$ 行，第一行表示初始树的答案。\n\n接下来 $m$ 行，表示每次修改后树的答案。\n\n[samples]\n\n## Background\n\nCTT2021 D3T1\n\n## Note\n\n- 子任务 $1$（$10$ 分）：保证满足 $2 \\leq n \\leq 500000$，$m = 0$。\n\n- 子任务 $2$（$20$ 分）：保证满足 $2 \\leq n \\leq 8000$，$0 \\leq m \\leq 8000$。\n\n- 子任务 $3$（$70$ 分）：保证满足 $2 \\leq n \\leq 500000$，$0\\leq m \\leq 500000$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8990","tags":["2021","O2优化","CTT（清华集训/北大集训）"],"sample_group":[["10 10\n2 1\n3 1\n4 2\n5 1\n6 4\n7 6\n8 5\n9 4\n10 1\n6 4 2 7 8 9 10 3 5\n6 7 10 7\n1 5 8 9\n1 2 10 8\n10 8 7 6\n2 4 2 9\n8 9 1 5\n5 8 8 2\n2 9 10 8\n10 7 4 10\n10 8 8 9\n","13\n15\n4\n6\n2\n2\n10\n7\n8\n8\n7\n"],["10 10\n2 1\n3 2\n4 3\n5 4\n6 2\n7 5\n8 7\n9 1\n10 8\n6 8 3 9 2 5 7 10 4 \n1 9 3 9\n4 5 2 7\n2 7 6 7\n8 10 10 1\n6 7 8 1\n3 9 9 8\n1 2 7 3\n2 3 2 9\n8 1 1 7\n2 9 2 8\n","3\n2\n2\n1\n2\n4\n4\n3\n3\n3\n3\n"]],"created_at":"2026-03-03 11:09:25"}}