# bzoj4543 [POI2014]Hotel加强版

### 题目描述

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

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.

### 输入格式

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


### 分析

$$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)$$

### 代码

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

const int N = 1e5+50;

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

Graph(): top(0) {
}

void add(int u, int v) {
}

void add2(int u, int v) {
}
} 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);
}
dfs(1, 0);
give(1);
dp(1, 0);
printf("%lld\n", ans);
return 0;
}


暂无评论