Submission #104769

#TimeUsernameProblemLanguageResultExecution timeMemory
104769puyu_liaoDuathlon (APIO18_duathlon)C++14
0 / 100
132 ms13148 KiB
#include<bits/stdc++.h> #include<stdint.h> using namespace std; #define IOS {cin.tie(0);ios_base::sync_with_stdio(false);} #define N 300005 #define int int64_t vector<int> v[N]; int sz[N]; int ans = 0,sum; void dfs(int x,int p){ sz[x] = 1; for(int i : v[x]) if(i != p){ dfs(i,x); sz[x] += sz[i]; } } void dfs2(int x,int p,int sp){ int cnt = v[x].size(); for(int i : v[x]) if(i != p){ dfs2(i,x,sz[x]-sz[i]); if(cnt>1)ans += sz[i] * (sum - sz[i] - 1); } if(cnt > 1) ans += sp * (sum - sp - 1); } int32_t main(){ IOS; int n,m,a,b; cin >> n >> m; for(int i=0;i<m;i++){ cin >> a >> b; v[a].push_back(b); v[b].push_back(a); } if(m!=n-1) return 0; dfs(1,1); //for(int i=1;i<=n;i++) cout << sz[i] << '\n'; sum = sz[1]; dfs2(1,1,0); cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...