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; }
|
未解决的问题