bzoj4543 [POI2014]Hotel加强版

题目描述

There are $n$ towns in Byteotia, connected with only $n-1$ roads.

Each road directly links two towns.

All the roads have the same length and are two way.

It is known that every town can be reached from every other town via a route consisting of one or more (direct-link) roads.

In other words, the road network forms a tree.

Byteasar, the king of Byteotia, wants three luxury hotels erected to attract tourists from all over the world.

The king desires that the hotels be in different towns and at the same distance one from each other.

Help the king out by writing a program that determines the number of possible locations of the hotel triplet in Byteotia.

题面翻译

给定一棵边权均为$1$的树,选三个点使得两两距离相等,问有几种选点方案。

输入格式

The first line of the standard input contains a single integer $n$ ($1 \le n \le 10^5$), the number of towns in Byteotia.

The towns are numbered from $1$ to $n$.

The Byteotian road network is then described in $n-1$ lines.

Each line contains two integers $a$ and $b$ ($1 \le a \le b \le n$) , separated by a single space, that indicate there is a direct road between the towns $a$ and $b$.

输出格式

The first and only line of the standard output should contain a single integer equal to the number of possible placements of the hotels.

样例输入

7
1 2
5 7
2 5
2 3
5 6
4 5

样例输出

5

分析

先尝试$O(n^2)$dp:设$f(i,j)$表示$i$子树中深度为$j$的点个数;$g(i,j)$表示$i$的子树中,两个点到$lca$的距离为$d$,$lca$到$i$的距离为$d-j$的点对数。也就是说,在$i$上连一条长度为$j$的链,则链头能与$i$子树中的点构成$g(i,j)$个合法答案。

如果设计好状态,转移应该不难,设当前合并点$u$的一个子树$v$:

$$ans += f(v,j) \cdot g(u,j+1)$$

$$ans += g(v,j) \cdot f(u,j-1)$$

$$g(u,j+1) += f(u,j+1)\cdot f(v,j)$$

$$g(u,j-1) += g(v,j)$$

$$f(u,j+1) += f(v,j)$$

这是一个$O(n^2)$的dp,但可以发现合并复杂度是子树高度,所以可以使用长链剖分优化到$O(n)$。

注意$g(v)$数组的起始位置为$g(u)$的前一位,所以在给一条长度为$len$的长链开空间时,需要开$2\cdot len-1$的空间。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 1e5+50;

struct Graph {
    struct Edge {
        int to, nxt;
    } e[N<<1];
    int top, head[N];

    Graph(): top(0) {
        memset(head, -1, sizeof head);
    }

    void add(int u, int v) {
        e[top] = (Edge){v, head[u]};
        head[u] = top++;
    }

    void add2(int u, int v) {
        add(u, v);
        add(v, u);
    }
} G;

int n;
int son[N], len[N];
ll pool1[N], pool2[N], *id1 = pool1, *id2 = pool2;
ll *f[N], *g[N], ans;

void dfs(int u, int fa) {
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa) continue;
        dfs(v, u);
        if (!son[u] || len[v] > len[son[u]])
            son[u] = v;
    }
    len[u] = len[son[u]] + 1;
}

void give(int u) {
    f[u] = id1;
    id1 += len[u];
    g[u] = id2 + len[u] - 1;
    id2 += len[u] * 2 - 1; 
}

void dp(int u, int fa) {
    if (son[u]) {
        f[son[u]] = f[u] + 1;
        g[son[u]] = g[u] - 1;
        dp(son[u], u);
    }
    f[u][0] = 1;
    ans += g[u][0];
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa || v == son[u]) continue;
        give(v);
        dp(v, u);
        for (int j = 0; j < len[v]; j++) {
            ans += f[v][j] * g[u][j+1];
            if (j) ans += g[v][j] * f[u][j-1];
        }
        for (int j = 0; j < len[v]; j++) {
            g[u][j+1] += f[u][j+1] * f[v][j];
            if (j) g[u][j-1] += g[v][j];
            f[u][j+1] += f[v][j];
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        G.add2(u, v);
    }
    dfs(1, 0);
    give(1);
    dp(1, 0);
    printf("%lld\n", ans);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论