Solution

这题的解法很妙啊... 考虑这三个点可能的形态: 令它们的重心为距离到这三个点都相同的节点, 则其中两个点分别在重心的两棵子树中, 且到重心的距离相等; 第三个点可能在重心的一棵不同于前两个点子树上, 也有可能在重心往上走可以到达的位置上.

定义数组\(f[i][j]\)表示在以\(i\)为根的子树下与\(i\)的距离为\(j\)的节点个数; \(g[i][j]\)表示在以\(i\)为根的子树下, 有多少个点对满足如下条件: 这个点对到它们LCA的距离相同, 我们假设其为\(d\), 则\(i\)到它们的LCA的距离为\(d - i\), 也就是说, 假如这两个点要找到一个在\(i\)上方的第三个点组成一组答案, 则第三个点到\(i\)的距离为\(j\).

考虑枚举每个点作为重心的情况. 进行一次DFS, 令\(u\)为当前点, \(v\)为\(u\)的一个子节点, 则有:

\[ ans += \sum_i g[u][i] \times f[v][i - 1] + g[v][i] \times f[u][i - 1] \\ g[u][i] += g[v][i + 1] + f[u][i] \times f[v][i - 1] \\ f[u][i] += f[v][i - 1] \\ \]

然后我们发现这种方法的转移是\(O(n^2)\)的... 考虑如何优化: 我们注意到, 当一个点\(u\)计算其第一个子节点时, 可以直接将\(f[u][i]\)赋值为\(f[v][i - 1]\), \(g[u][i]\)赋值为\(g[v][i + 1]\), 因此在计算完这个子节点后, 直接对返回的数组指针进行位移就可以得到当前点的\(f\)和\(g\). 因此考虑采用按深度树链剖分的方法, 从重儿子处继承\(f\)和\(g\)数组.

时间复杂度: \(O(n)\). 为什么? 不会证. 以后学了长链剖分再填坑吧.

由于数组是动态开的, 同时还存在指针变化的操作, 因此边界可能比较难计算. 假如你比较懒, 就直接将数组大小/对答案贡献的范围调大一些, 这样可以省去不少麻烦.

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
          namespace Zeonfai{    inline int getInt()    {        int a = 0, sgn = 1;        char c;        while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;        while(isdigit(c)) a = a * 10 + c - '0', c = getchar();        return a * sgn;    }}const int N = (int)5e4;int n;struct result{    long long *first, *second;    inline result() {}    inline result(long long *_first, long long *_second)    {        first = _first; second = _second;    }};long long ans;struct tree{    struct node    {        std::vector
         
           edg; int maxDepth, dep; node *hvy; inline void clear() { edg.clear(); hvy = NULL; } }nd[N + 1]; inline void clear() { for(int i = 1; i <= n; ++ i) nd[i].clear(); } inline void addEdge(int u, int v) { nd[u].edg.push_back(nd + v); nd[v].edg.push_back(nd + u); } void getDepth(node *u, node *pre) { u->maxDepth = u->dep = pre == NULL ? 0 : pre->dep + 1; for(auto v : u->edg) if(v != pre) { getDepth(v, u); u->maxDepth = std::max(u->maxDepth, v->maxDepth); if(u->hvy == NULL || v->maxDepth > u->hvy->maxDepth) u->hvy = v; } } result decomposition(node *u, node *pre, node *tp) { result res; long long *f, *g; if(u->hvy != NULL) res = decomposition(u->hvy, u, tp), f = res.first - 1, g = res.second + 1; else { int len = u->dep - tp->dep + 10; //懒得想边界了, 直接开大一些, 求对答案的时候也求多一些就可以了 f = new long long[len << 1]; memset(f, 0, len << 1 << 3); f += len; g = new long long[len << 1]; memset(g, 0, len << 1 << 3); } f[0] = 1; ans += g[0]; for(auto v : u->edg) if(v != pre && v != u->hvy) { int len = v->maxDepth - v->dep + 1; res = decomposition(v, u, v); long long *_f = res.first, *_g = res.second; for(int i = 1; i <= len; ++ i) ans += g[i] * _f[i - 1] + _g[i] * f[i - 1]; for(int i = 1; i <= len; ++ i) g[i] += _f[i - 1] * f[i]; for(int i = 0; i <= len; ++ i) g[i] += _g[i + 1]; for(int i = 1; i <= len; ++ i) f[i] += _f[i - 1]; } return result(f, g); }}T;int main(){ #ifndef ONLINE_JUDGE freopen("thr.in", "r", stdin); freopen("thr.out", "w", stdout); #endif using namespace Zeonfai; while(n = getInt()) { T.clear(); for(int i = 1; i < n; ++ i) { int u = getInt(), v = getInt(); T.addEdge(u, v); } T.getDepth(T.nd + 1, NULL); ans = 0; T.decomposition(T.nd + 1, NULL, T.nd + 1); printf("%lld\n", ans); }}
         
        
       
      
     
    

---

update Wed, Aug 30:

长链剖分不过也就是这么一个东西罢了.

长链剖分解决的是什么问题? 比如说给你一棵树, 每个节点有一个点权, 要求统计以每个点为根的子树下每个深度的点的最大权值是多少.

考虑普通的轻重链剖分, 时间复杂度为\(O(n \log n)\). 非常容易分析, 一条重链上的点共用一个数组, 因此从重儿子更新父亲的时间为\(O(1)\), 只需要移动数组指针即可; 一个点作为最大权值往上更新, 跳虚边的次数最多为\(\log n\)次, 因此时间复杂度\(O(n \log n)\).

这个复杂度实际上已经很优秀了, 并且在实际上这个\(\log\)还通常跑不满. 尽管如此, 我们仍然有时间复杂度更优秀的线性做法. 考虑采取另一种树剖的策略, 按照深度剖分而非轻重. 我们令\(d_u\)表示以\(u\)为根的子树中节点的最大深度, 则处理每个点\(u\)的时间复杂度为\(\sum_{v为u的儿子}d_v - (d_u - 1)\), 其中减去的部分是由重儿子直接传上来而无需复制的部分, 则总的复杂度为

\[ \begin{aligned} \sum_u(\sum_v d_v - (d_u - 1)) &= \sum_{u为非根节点} d_u - \sum_{u为非叶子节点} d_u + n \\ &= \sum_{u, u为叶子节点} d_u - \sum_{u为根节点} d_u + n \end{aligned} \]

我们又有, 以一个叶子节点为根的子树的最大深度为1, 因此长链剖分解决这个问题的时间复杂度为\(O(n)\).