bzoj3522: [Poi2014]Hotel 長鍊剖分+樹形DP

bzoj3522\4543: [Poi2014]Hotel

Description

有一個樹形結構的飯店，n個房間，n-1條無向邊，每條邊的長度相同，任意兩個房間可以互相到達。吉麗要給他的三個妹子各開（一個）房（間）。三個妹子住的房間要互不相同（否則要打起來了），為了讓吉麗滿意，你需要讓三個房間兩兩距離相同。

有多少種方案能讓吉麗滿意？

Input

第一行一個數n。

接下來n-1行，每行兩個數x,y，表示x和y之間有一條邊相連。

Output

讓吉麗滿意的方案數。

Sample Input

7

1 2

5 7

2 5

2 3

5 6

4 5

Sample Output

5

HINT

【樣例解釋】

{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}

【資料範圍】

n≤5000(bzoj4543是1e5)

Source

By Dzy

分析

首先一句話題意：求樹上三點兩兩相同的無序點對個數

轉化一下顯然轉化到三點都某同一點的距離相等。

考慮dfs并統計子樹内的答案。

顯然答案隻能分為如下兩種

我們先考慮前兩個點 u,v u , v 深度（到子樹根的距離，下同）要一樣，那麼他們到lca的距離也一樣，假設他們到lca的距離為d，lca深度為a，我們發現不管是哪種情況，w到根的距離都是d-a。

d-a不夠優美，于是我們假設lca的深度為d-a，那麼w到根的距離就是a了。

fi,j f i , j 表示以i為根的子樹深度為j的點的個數。

gi,j g i , j 表示以i為根的子樹到lca的距離和lca到根距離差為j的點對個數。

首先考慮答案，我們用合并子樹的方式進行樹形DP_

那麼有 ans=fu,j−1∗gv,j=+gu,j∗fv,j−1 a n s = f u , j − 1 ∗ g v , j = + g u , j ∗ f v , j − 1

u u 是vv的父親，考慮 (u,v) ( u , v ) 這條邊不難得出這個方程。

考慮 f,g f , g 的轉移

首先考慮繼承子樹中的答案 fu,j=fv,j−1,gu,j=gv,j+1 f u , j = f v , j − 1 , g u , j = g v , j + 1

其次我們發現，合并子樹中也會産生新的g點對，于是

gu,j=gv,j+1+fu,j⋅fv,j−1 g u , j = g v , j + 1 + f u , j ⋅ f v , j − 1

時間複雜度 O(n2) O ( n 2 )

知識點：長鍊剖分

參照文章：長鍊剖分

大緻思路和樹鍊剖分一樣，隻不過剖分的依據變成了深度。

這個東西可以奇迹般地做到 O(n) O ( n )

但是注意這個複雜度沒有算父親對子樹的繼承，僅僅是合并階段，而且轉移複雜度必須和深度有關。

是以對于子樹轉移的那部分用指針來搞。這題就變成 O(n) O ( n ) 的了

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N =  + ;
typedef pair<int, int> pa;
int read() {
    char ch = getchar(); int x = , f = ;
    for(;ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -;
    for(;ch >= '0' && ch <= '9'; ch = getchar()) x = (x << ) + (x << ) - '0' + ch;
    return x * f;
}
int pre[N], nxt[N << ], to[N << ], d[N], son[N], top, n;
long long ans, mem[N * ];
long long *g[N], *f[N], *it = mem + ; 
void add(int u, int v) {to[++top] = v; nxt[top] = pre[u]; pre[u] = top;}
void adds(int u, int v) {add(u, v); add(v, u);}
void New(int x, int siz) {f[x] = it; it += (siz << ); g[x] = it; it += siz;}
void Dfs(int u, int fa) {
    d[u] = ; son[u] = ;
    for(int i = pre[u]; i; i = nxt[i]) 
    if(to[i] != fa) {
        Dfs(to[i], u);
        d[u] = max(d[u], d[to[i]] + );
        if(!son[u] || d[to[i]] > d[son[u]]) son[u] = to[i];
    }
}
void Dp(int u, int fa) {
    if(son[u]) {
        f[son[u]] = f[u] + ; g[son[u]] = g[u] - ;
        Dp(son[u], u);
    }
    f[u][] = ; ans += g[u][];
    for(int i = pre[u]; i; i = nxt[i])
    if(to[i] != fa && to[i] != son[u]) {
        New(to[i], d[to[i]] + ); Dp(to[i], u);
        for(int j = d[to[i]]; ~j; --j) { //get_ans && update g[u]
            if(j) ans += f[u][j - ] * g[to[i]][j];
            ans += g[u][j + ] * f[to[i]][j];
            g[u][j + ] += f[u][j + ] * f[to[i]][j];
        }
        for(int j = ; j <= d[to[i]]; ++j) { //Merge
            if(j) g[u][j - ] += g[to[i]][j];
            f[u][j + ] += f[to[i]][j];
        }
    }
}
int main() {
    n = read();
    for(int i = ;i < n; ++i) {
        int u = read(), v = read();
        adds(u, v);
    }
    Dfs(, ); New(, d[] + ); Dp(, );
    printf("%lld\n", ans);
    return ;
}