Editorial for Bedao Grand Contest 02 - LITPATH
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> using namespace std; #define tag "LITPATH" #define maxn 100007 #define forinc(i,a,b) for(int i=a;i<=b;i++) #define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); } /// my data: using unlong = unsigned long long; #define long long long struct neigh{ int ver,wei; }; ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> int n; int64_t ans; vector<neigh> adj[maxn]; int f[maxn][4]; ///0 --> 00 ///1 --> 11 ///2 --> 10 ///3 --> 01 void dfs(int u=1,int p=0){ for(auto nei: adj[u]){ int v=nei.ver; int w=nei.wei; if(v==p) continue; dfs(v,u); ++f[v][w]; if(w){ ans+=f[v][1]<<1; ans+=f[v][0]; ans+=f[v][2]; ans+=(int64_t)f[u][0]*f[v][1]; ans+=(int64_t)f[u][1]*f[v][0]; ans+=(int64_t)f[u][1]*f[v][1]<<1; ans+=(int64_t)f[u][1]*f[v][2]; ans+=(int64_t)f[u][2]*f[v][1]; f[u][1]+=f[v][1]; f[u][2]+=f[v][2]+f[v][0]; }else{ ans+=(int64_t)(f[u][0]+1)*f[v][1]; ans+=(int64_t)(f[u][0]+1)*f[v][3]; ans+=(int64_t)(f[u][0]+1)*f[v][0]<<1; ans+=(int64_t)f[u][1]*f[v][0]; ans+=(int64_t)f[u][3]*f[v][0]; f[u][0]+=f[v][0]; f[u][3]+=f[v][3]+f[v][1]; } } } void enter(){ cin>>n; int u,v,w; forinc(i,2,n) cin>>u>>v>>w,adj[u].push_back({v,w}),adj[v].push_back({u,w}); } void solve(){ dfs(); cout<<ans<<"\n"; } int main() { checkfile(tag); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); enter(); solve(); return 0; }
Comments