题目链接
http://west14.openjudge.cn/verywater/0027/
分析
补集转化，关键在于求出有多少场会议不需要额外场地；
假设已确定两场会议的位置，若第三场会议的位置在这两点的路径上，是符合要求的；
而在两端确定的情况下，这样的点只有两端间路径长度
−
1
-1
−1 个；
统计出所有路径的长度再减去路径数量即为答案；
每条边会对所有路径长度之和贡献
s
i
z
e
[
v
]
∗
(
n
−
s
i
z
e
[
v
]
)
size[v] * (n - size[v])
size[v]∗(n−size[v])；
s
i
z
e
[
v
]
size[v]
size[v] 是以该边深度较大点为根的子树大小；
路径数量则可以在DFS某点时，用新子树数量乘已有子树数量（包括该点）累加得到。
AC代码
#include <cstdio>
inline int read() {
int num
= 0;
char c
= getchar();
while (c
< '0' || c
> '9') c
= getchar();
while (c
>= '0' && c
<= '9')
num
= num
* 10 + c
- '0', c
= getchar();
return num
;
}
const int maxn
= 1e5 + 5;
int head
[maxn
], eid
;
struct Edge
{
int v
, next
;
} edge
[2 * maxn
];
inline void insert(int u
, int v
) {
edge
[++eid
].v
= v
;
edge
[eid
].next
= head
[u
];
head
[u
] = eid
;
}
int n
, size
[maxn
];
long long ans
= 0;
void dfs(int u
, int fa
) {
size
[u
] = 1;
for (int p
= head
[u
]; p
; p
= edge
[p
].next
) {
int v
= edge
[p
].v
;
if (v
== fa
) continue;
dfs(v
, u
);
ans
-= 1ll * size
[v
] * (n
- size
[v
]) - 1ll * size
[u
] * size
[v
];
size
[u
] += size
[v
];
}
}
int main() {
n
= read();
for (int i
= 1; i
< n
; ++i
) {
int u
= read(), v
= read();
insert(u
, v
), insert(v
, u
);
}
ans
= 1ll * n
* (n
- 1) * (n
- 2) / 6;
dfs(0, -1);
printf("%lld", ans
);
return 0;
}
