对于一条连接叶子的边 (,)我们用 1 表示他的特征值如果其中的叶子是 min(,) 则特征值为 1否则为 0。直接用长度为 −1 的字符串表示每条边的特征值即可。菊花这是简单的先用 1 表示第一条边的特征值那么不用被删的点就是根对于之后的边只需要保留上一条边没有被删的点即可。于是我们可以总结出一个策略策略一如果当前边与上一条边有公共点那么保留公共点删除另一个点。链只考虑链的话也是简单的从左往右删同样只需要知道第一条边的特征值之后每次删除上一条边出现过的点即可。但是这个策略和策略一完全矛盾考虑换个思路。我们钦定这条链的中点为根如果链上有偶数个点那么中点在一条边上交替删除左链和右链的叶子我们先用 2 表示开头删除的两条边的特征值对于之后的边如果满足策略一就遵循策略一否则策略二如果当前边的某个点在之前出现过且不是在上一条边出现的那么删除这个点。举个例子以偶数个点为例在删到只剩两个点之前会一直遵循策略二显然合法对于最后两个点假如在上图中先按顺序删除了 3,4 之后还剩下 (1,2) 这条边由于上一条边是 (2,4) 所以会遵循策略一删除 1 号点。如果是奇数个点的情况不难验证我们最后会恰好剩下钦定的根节点。但是现在我们多用了 1考虑优化假设开头两条边是 (,),(,) 我们需要根据他们的某种关系在只知道一条边的特征值的情况下就能推出另一条边的特征值。一种比较简单的方法是设计两条边的某种偏序关系那么如果 (,),(,) 的特征值一样就把大的那条边放在前面否则把小的那条边放在前面这样我们在得到第二条边时只需要根据他和第一条边的大小关系就能知道他的特征值是啥了。你可以把这个偏序关系设成你喜欢的任何类型只需要保证他是确定且严格的就可以了比如比较一条边构成的无序二元组的字典序。正解首先需要明确的是我们唯一能提供的 1 一定是给出第一条边的特征值否则 Kathrin 将啥都不知道。既然我们考虑过链的情况了那么对于一般树一种经典的思路就是拉出直径在后面我们会说明选直径的用处。同样以直径的中点为根注意如果直径有偶数个点那么会有两个深度为 1 的点。我们遇到的第一个问题是树上可能会有好多完全不相干的叶子而我们只能提供其中一个叶子的信息但不妨先假设我们能通过魔法直接得到一条叶边的特征值。我们先取出所有点 满足 的每个儿子都是叶子然后使用魔法得到其中某条边的特征值删掉他之后按照菊花的思路一直用策略一直到把所有儿子都删光。接下来我们按照深度从大往小一层层删点假设当前删第 层考虑第 −1 层的某个点 他的儿子现在肯定全都是叶子了有些一开始就是叶子有些后来才变成叶子由于我们已经提前把只有叶子儿子的点处理了所以他必定有一个儿子 是后来才变成叶子的也就是说 曾经在某条被删的边出现过那么就可以用策略二把 删掉之后就可以一直用策略一把他的其他儿子全都删掉。注意如果这个选择的 是第 层第一个被删的点那么他不能是第 1 层最后删掉的点的父亲否则在考虑 (,) 这条边时Kathrin 会错误地使用策略一导致把 给删了。不过由于我们在一开始选择了直径中点为根所以此时第 层至少有两个点我们一定能选出某个合法的 。好了现在我们只需要解决魔法的事了我们取出所有需要知道特征值的叶边 (,)根据链最后部分的思路我们需要把他们按照某种顺序排列使得如果 (1,1)(,) 则他们的特征值相同否则不同这样我们只需要知道第一条边的特征值就好了。实现这个顺序也是简单的只需要把他们先从小到大排好序然后reverse所有极长特征值相同的段即可。Kathrin 想要判断一条边是否是需要使用魔法的叶边只需要判断这条边的两个点是否都没有出现过即可。codeKathrin 只需要按照策略无脑执行就可以了但是 Ann 要考虑的就很多了......cpp#includebits/stdc.h #define Debug puts(-------------------------) #define eb emplace_back #define PII pairint,int #define fi first #define se second #define mk make_pair using namespace std; const int N1e35; int OP,n; namespace Ann{ int p,q,dep[N],fa[N],mxdep,deg[N],lst_del; vectorint G[N],vec[N],ans; bool appear[N],del[N]; //在之前是否出现过是否被删掉了 char begin_op; int find_kfa(int x,int k){ while(k) xfa[x],k--; return x; } void dfs0(int u,int f,int rt){ dep[u]dep[f]1; if(!rt||dep[u]dep[rt]) rtu; fa[u]f; for(int v:G[u]) if(v!f) dfs0(v,u,rt); } void dfs1(int u,int f,int d){ vec[d].eb(u),fa[u]f,dep[u]d,mxdepmax(mxdep,dep[u]); for(int v:G[u]) if(v!f) dfs1(v,u,d1),deg[u]; } int op(int u,int son){ return sonu; } void remove(int u){ if((int)ans.size()n-1) return; // if(del[u]){ // cerrWrong!!!the node u is already removeendl; // exit(0); // } del[u]appear[u]true,lst_delu; ans.eb(u); } void clear_leaf(int u){ //删除 u 的所有儿子 if(!u) return; appear[u]true; for(int v:G[u]) if(fa[v]u!del[v]) remove(v);