{"problem":{"name":"BZOJ3779 重组病毒","description":{"content":"实验在一个封闭的局域网内进行。局域网内有 $n$ 台计算机，编号为 $1\\sim n$。一些计算机之间通过网线直接相连，形成树形的结构。局域网中有一台特殊的计算机，称之为核心计算机。根据一些初步的研究，研究员们拟定了一个一共 $m$ 步的实验。实验开始之前，核心计算机的编号为 $1$，每台计算机中都有病毒的一个变种，而且每台计算机中的变种都不相同。实验中的每一步会是下面中的一种操作： - `RE","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":"LGP10661"},"statements":[{"statement_type":"Markdown","content":"实验在一个封闭的局域网内进行。局域网内有 $n$ 台计算机，编号为 $1\\sim n$。一些计算机之间通过网线直接相连，形成树形的结构。局域网中有一台特殊的计算机，称之为核心计算机。根据一些初步的研究，研究员们拟定了一个一共 $m$ 步的实验。实验开始之前，核心计算机的编号为 $1$，每台计算机中都有病毒的一个变种，而且每台计算机中的变种都不相同。实验中的每一步会是下面中的一种操作：\n\n- `RELEASE x`。在编号为 $x$ 的计算机中植入病毒的一个新变种。这个变种在植入之前不存在于局域网中。\n- `RECENTER x`。将核心计算机改为编号为 $x$ 的计算机。但是这个操作会导致原来核心计算机中的病毒产生新变种，并感染过来。换言之，假设操作前的核心计算机编号为 $y$，相当于在操作后附加了一次 `RELEASE y` 的操作。\n\n根据研究的结论，在植入一个新变种时，病毒会在局域网中搜索核心计算机的位置，并沿着网络中最短的路径感染过去。\n\n而第一轮实验揭露了一个惊人的真相：病毒的不同变种是互斥的。新变种在感染一台已经被旧变种感染的电脑时，会把旧变种完全销毁之后再感染。但研究员发现了实现过程中的漏洞。如果新变种在感染过程中尚未销毁过这类旧变种，需要先花费 $1$ 单位时间分析旧变种，才能销毁。如果之前销毁过这类旧变种，就可以认为销毁不花费时间。病毒在两台计算机之间的传播亦可认为不花费时间。\n\n研究员对整个感染过程的耗时特别感兴趣，因为这是消灭病毒的最好时机。于是在 $m$ 步步实验之中，研究员有时还会做出如下的询问：\n\n- `REQUEST x`。询问如果在编号为 $x$ 的计算机的关键集合中的计算机中植入一个新变种，平均感染时间为多长。编号为 $y$ 的计算机在编号为 $x$ 的计算机的关键集合中，当且仅当从 $y$ 沿网络中的最短路径感染到核心计算机必须经过 $x$。由于有 `RECENTER` 操作的存在，这个集合并不一定是始终不变的。\n\n至此，安全机构认为已经不需要实际的实验了，于是他们拜托你编写一个程序，模拟实验的结果，并回答所有的询问。\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $m$，分别代表局域网中计算机的数量，以及操作和询问的总数。\n\n接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，表示局域网中编号为 $x$ 和 $y$ 的计算机之间有网线直接相连。\n\n接下来 $m$ 行，每行包含一个操作或者询问，格式如问题描述中所述。\n\n## Output\n\n对于每个询问，输出一个实数，代表平均感染时间。输出与答案的绝对误差不超过 $10^{-6}$ 时才会被视为正确。\n\n[samples]\n\n## Background\n\n黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和变异能力极强。为了阻止这种病毒传播，某安全机构策划了一次实验，来研究这种病毒。\n\n## Note\n\n对于 $100\\%$ 的数据，$1\\leq n\\leq 10^5$，$1\\leq m\\leq 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10661","tags":["Special Judge","O2优化","动态树 LCT"],"sample_group":[["8 6\n1 2\n1 3\n2 8\n3 4\n3 5\n3 6\n4 7\nREQUEST 7\nRELEASE 3\nREQUEST 3\nRECENTER 5\nRELEASE 2\nREQUEST 1","4.0000000000\n2.0000000000\n1.3333333333"]],"created_at":"2026-03-03 11:09:25"}}