AK-dream
博客
标签
归档
友链
关于
博客
标签
归档
友链
关于
AK-dream
博客
标签
归档
友链
关于
false
true
战略游戏[SDOI2018]
https://www.luogu.com.cn/problem/P4606 题解每次是试图摧毁一个城市和它连着的所有边,发现如果摧毁的不是一个割点那么就不会有任何影响,所以先建出原图的圆方树 每次选择了若干个关键节点,建出这些关键节点在圆方树上的虚树,有一个显而易见的结论: 答案即为虚树上(包括在虚树的某条边上)所有非关键节点的圆点个数 虚树上所有的叶子节点都一定是关键节点 断掉一个非关键...
2021-01-04
阅读全文
暴力写挂[CTSC2018]
题目描述给定两棵树$T$和$T’$ 求$$\max(\operatorname{depth}(x) + \operatorname{depth}(y) - ({\operatorname{depth}(\operatorname{LCA}(x,y))}+{\operatorname{depth’}(\operatorname{LCA’}(x,y))}))$$ 注:带[$’$]的表示第二棵树 ...
2020-07-27
阅读全文
世界树[HNOI2014]
题目描述题目背景太长不放 传送门 给你一棵$n$个节点的树,有$q$次询问,每次指定$m_i$个节点为关键节点;对于任意一个节点,它被距离自己树上距离最近的那个关键节点管辖;输出每个关键节点各管辖多少个节点 $n,, q \le 300000$,$\sum m_i\le 300000$ 题解看到$\sum m_i\le 300000$想到什么了?虚树! 所以我们把关键节点的虚树建出来,然后考...
2020-06-12
阅读全文