战略游戏[SDOI2018]

https://www.luogu.com.cn/problem/P4606 题解每次是试图摧毁一个城市和它连着的所有边,发现如果摧毁的不是一个割点那么就不会有任何影响,所以先建出原图的圆方树 每次选择了若干个关键节点,建出这些关键节点在圆方树上的虚树,有一个显而易见的结论: 答案即为虚树上(包括在虚树的某条边上)所有非关键节点的圆点个数 虚树上所有的叶子节点都一定是关键节点 断掉一个非关键...

暴力写挂[CTSC2018]

题目描述给定两棵树$T$和$T’$ 求$$\max(\operatorname{depth}(x) + \operatorname{depth}(y) - ({\operatorname{depth}(\operatorname{LCA}(x,y))}+{\operatorname{depth’}(\operatorname{LCA’}(x,y))}))$$ 注:带[$’$]的表示第二棵树 ...

世界树[HNOI2014]

题目描述题目背景太长不放 传送门 给你一棵$n$个节点的树,有$q$次询问,每次指定$m_i$个节点为关键节点;对于任意一个节点,它被距离自己树上距离最近的那个关键节点管辖;输出每个关键节点各管辖多少个节点 $n,, q \le 300000$,$\sum m_i\le 300000$ 题解看到$\sum m_i\le 300000$想到什么了?虚树! 所以我们把关键节点的虚树建出来,然后考...