Hotels

题目描述： 给定一棵树，在树上选 \(3\) 个点，要求两两距离相等，求方案数。 数据范围： \(1\le n\le 5000\) \(1\le a,b\le n\) 思路： 一开始我想的就是枚举两个点，然后处理第三个点。 但是发现这样做非常的不正确，并且非常容易算重，所以我舍去了这种方式。 但是在 ......

三倍经验： bzoj #3522 P3565 loj #2431 加强版： bzoj #4543 先看 bzoj #3522 这题。容易想到时间 \(O(n^2)\) ，空间 \(O(n^2)\) 的树形 dp 。设 \(dp_{1/2/3, u, i}\) 表示以 \(u\) 为根的子树中所有以 ......

[POI2014] HOT-Hotels 题面翻译 给定一棵树，在树上选 \(3\) 个点，要求两两距离相等，求方案数。 题目描述 There are \(n\) towns in Byteotia, connected with only \(n-1\) roads. Each road dire ......

自然的想法是枚举共同的交点，然后进行换根 dp，复杂度可以做到 $\mathcal O(n^2)$，可以通过简单版，但是显然过不了 $10^5$ 的数据，考虑进行优化。  ......

长链剖分优化 DP 板子题了，但是虽然是板子这个转移方程也很难想。 ## problem 树。求 $\sum_{1\leq i 点击查看代码 Rename $height,len\to hei$，$g\to h$。 ``` #include #include #include #include us ......

[传送门](https://www.luogu.com.cn/problem/P5904) ## 题意 给定一棵树，求树上存在多少个三元组 $(a,b,c)$，满足 $\operatorname{dis}(a,b)=\operatorname{dis}(a,c)=\operatorname{dis} ......