cf-482 div2

cf补题
我好想对一些特殊的条件的判断非常的不敏感,差点爆零。
特殊情况的判断一定要敏感!!!

A

找规律,偶数块除2,奇数块直接输出答案。
注意n=0时候的特判。。。hack场

B

还是没有注意到特殊边界的判断。。。
当n=1时,且美丽值已经达到最大的时候,最大的美丽值为len-1…
我真的没有想到这种特殊情况的判断啊。

C

x, y两端的点数相乘即可,用dfs来统计点的个数。
用了补的思想

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
typedef long long ll;
vector<int> G[maxn];
ll n, x, y;
int depth[maxn];
int dfs(int u, int v, int p){
int ans = 1;
for(int i=0; i<G[u].size(); i++){
int temp = G[u][i];
if(temp == v) continue;
else if(temp == p) continue;
else {
ans += dfs(temp, v, u);
}
}
return ans;
}
bool vis[maxn];
void bfs(int u){
memset(depth, 0, sizeof(depth));
memset(vis, 0, sizeof(vis));
queue<int> q;
q.push(u);
vis[u] = true;
while(!q.empty()){
int temp = q.front();
q.pop();
for(int i=0; i<G[temp].size(); i++){
int v = G[temp][i];
if(vis[v]) continue;
else{
depth[v] = depth[temp]+1;
q.push(v);
vis[v] = true;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>x>>y;
for(int i=0; i<n-1; i++){
int u, v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
ll num1 = dfs(x, y, -1);
ll num2 = dfs(y, x, -1);
cout<<n*(n-1)-(n-num1)*(n-num2)<<endl;
return 0;
}

未解决的问题

文章目录
  1. 1. A
  2. 2. B
  3. 3. C
    1. 3.1. AC代码
  4. 4. 未解决的问题
{{ live2d() }}