[题目链接](F - Add One Edge 2 (atcoder.jp))
Problem Statement
You are given a tree with N N N vertices. The i i i-th edge ( 1 ≤ i ≤ N − 1 ) (1 \leq i \leq N-1) (1≤i≤N−1) connects vertices u i u_i ui and v i v_i vi bidirectionally.
Adding one undirected edge to the given tree always yields a graph with exactly one cycle.
Among such graphs, how many satisfy all of the following conditions?
- The graph is simple.
- All vertices in the cycle have degree 3 3 3.
中文题意
问题陈述
给你一棵有 N N N 个顶点的树。 i − t h i -th i−th 边 ( 1 ≤ i ≤ N − 1 ) (1 \leq i \leq N-1) (1≤i≤N−1) 双向连接顶点 u i u_i ui 和 v i v_i vi 。
在给定的树上添加一条无向边会得到一个有一个循环的图。
在这些图中，有多少个满足以下所有条件？
- 图很简单。
- 循环中的所有顶点都有度数 3 3 3 。
Constraints
- 3 ≤ N ≤ 2 × 1 0 5 3 \leq N \leq 2 \times 10^5 3≤N≤2×105
- 1 ≤ u i , v i ≤ N 1 \leq u_i, v_i \leq N 1≤ui,vi≤N
- The given graph is a tree.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
N
N
u
1
u_1
u1
v
1
v_1
v1
u
2
u_2
u2
v
2
v_2
v2
⋮
\vdots
⋮
u
N
−
1
u_{N-1}
uN−1
v
N
−
1
v_{N-1}
vN−1
Output
Print the answer.
Sample Input 1
6
1 2
2 3
3 4
4 5
3 6
Sample Output 1
1
Adding an edge connecting vertices 2 2 2 and 4 4 4 yields a simple graph where all vertices in the cycle have degree 3 3 3, so it satisfies the conditions.
Sample Input 2
7
1 2
2 7
3 5
7 3
6 2
4 7
Sample Output 2
0
There are cases where no graphs satisfy the conditions.
Sample Input 3
15
1 15
11 14
2 10
1 7
9 8
6 9
4 12
14 5
4 9
8 11
7 4
1 13
3 6
11 10
Sample Output 3
6
解法
考虑，新增加一条边必然会使得所连接的两个点的度数
+
1
+ 1
+1。现在要求环上的所有节点的度数都为
3
3
3 ，在这里我们可以对目前树中部分度数为3的点视为一个连通块。然后我们对于每一个顶点，依次统计一下与其相连的节点度数是否为
2
2
2。如果是
2
2
2，将 cnt 的数量
+
1
+1
+1 ，因为每次连接成环的话，是选择其中两个顶点，那么最后的答案数为
C
n
2
C_{n}^{2}
Cn2 。
typedef long long LL;
std::vector<int> G[N];
int deg[N];
bool visit[N];
LL cnt, ans;
void dfs(int v, int fa = 0) {
if(deg[v] != 3) {
// v是一个周边的点
cnt += (deg[v] == 2);
return ;
}
visit[v] = 1;
for (auto x : G[v]) {
if(x == fa) continue;
dfs(x, v);
}
}
void solved() {
/* your code */
int n;
cin >> n;
for (int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v;
G[u].push_back(v); G[v].push_back(u);
deg[u] ++, deg[v] ++;
}
for (int i = 1; i <= n; i ++) {
//找度数为3的连通块
if(deg[i] != 3) continue;
if(visit[i]) continue;
cnt = 0;
dfs(i);
ans += 1LL * cnt * (cnt - 1) / 2;
}
cout << ans << endl;
}
总结
本道题目，看似是一个树的题目。我们将其转化为了一个dfs 型的联通块计算题目。然后使用组合计数即可。