打表骗分过样例,暴力搜索出奇迹

百般乐器,唢呐为王.不是升天,就是拜堂.

大风起兮云飞扬，意大利炮轰他娘

巴山楚水凄凉地，蜜雪冰城甜蜜蜜

但使龙城飞将在，Come on baby don't be shy

问君能有几多愁，累了困了喝红牛

垂死病中惊坐起，吃席麻烦先随礼

美国疯光,千里兵疯，万里血飘。

望白宫内外，人心惶惶。

美国上下，顿时逃逃。

自己找死，到处装逼。

欲与世界试比高！

须晴日，看坟墓连绵，分外妖娆。

总统如此作妖，引无数老美竞折腰。

笑美佩洛西，尽输文采。

拜登傻子，更逊风骚。

一代混混，美特朗普，只识散谣保沙雕。

俱往矣。数沙雕人物。总统最高!

什么叫摔伤？从楼上掉下来。

什么叫幸运？楼下有个草堆。

什么叫不幸？草堆上有个叉子。

什么叫希望？没掉在叉子上。

什么叫绝望？也没掉在草堆上。

什么叫多亏了？掉在水里。

什么叫完蛋？水里有鲨鱼。

什么叫幸好？猎人在旁边一枪打中了鲨鱼。

什么叫结束？猎人射的是散弹。

什么叫上天眷顾？没射中你。

什么叫大难临头？你不会游泳。

什么叫万幸？你在浅水区。

什么叫天要亡我？水里的海草缠住了脚。

什么叫必有后福？海草一挣就断。

什么叫必有补刀？猎人瞄准了你。

什么叫虚惊一场？猎人要射杀你头上的水鸟。

什么叫冥王想你？猎人手一抖……

砰！

剪辣椒chilli

假设根为1,设删去的点意为这个点到其父亲的连边被删了,关系指一个点是另一个点的祖先,size[x]为以x为根的子树大小,a,b,c是三棵新子树的大小。

答案即为ans=max(a,b,c)−min(a,b,c)

那么只会有两种情况：

1. 被删去的点有关系 不妨设x是y的祖先 a=size[y],b=size[x]−size[y],c=n−size[x]
2. 被删去的点无关系 a=size[x],b=size[y],c=n−size[x]−size[y]

显然这里就有一种比较暴力的方法了，时间复杂度O(n^2),所以考虑优化。

在dfs中，我们维护两个set:A,B

1. 当进入点x时，把size[x]放入A中；
2. 当走出点x时，把size[x]从A中删除并放入B中；

这样A里的元素就是x的直接祖先，B中是与x无关系的点（不需要考虑到还没有访问到的点，因为反过来会遍历到的）

接下来每到一个点x，我们继续考虑两种情况：

1. 被删去的点有关系 假如我们要删去点x，另一个被删去的点为y应使得n−size[y]和size[y]−size[x]这两个子树的大小最平均，即n−size[y]=size[y]−size[x]⇒2size[y]=n+size[x]。 那么我们就去A中找一个值接近上面size[y]的值并更新答案。 当然，不一定会有正好相等的，应该用lower_bound()后在让指针iter--，进行两次判断。
2. 被删去的点无关系 同理假如我们要删去点x和与它无关系的点y，就要使得size[y]和n−size[x]−size[y]这两个值最相近，即size[y]=n−size[x]−size[y]⇒2size[y]=n−size[x]。 那么我们就去B中找一个值接近上面sizey的值并更新答案。