This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3142 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../tools/chminmax.cpp" #include "../../tools/fixpoint.cpp" #include "../../tree/centroid.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n; cin>>n; Centroid G(n); for(int i=1;i<n;i++){ int u,v; cin>>u>>v; u--;v--; G.add_edge(u,v); } vector<ll> as(n),bs(n); for(int i=0;i<n;i++) cin>>as[i]; for(int i=0;i<n;i++) cin>>bs[i]; using P = pair<int, ll>; vector<vector<P>> H(n); MFP([&](auto dfs,int v,int p)->ll{ ll res=as[v]-bs[v]; for(int u:G[v]){ if(u==p) continue; ll tmp=dfs(u,v); H[u].emplace_back(v,-tmp); H[v].emplace_back(u,+tmp); res+=tmp; } return res; })(0,-1); vector<ll> dp(n,0); queue<int> que; que.emplace(G.build(0)[0]); vector<ll> tmp(n); while(!que.empty()){ int r=que.front();que.pop(); for(int t=0;t<2;t++){ ll res=0; for(auto ch:H[r]){ int c=ch.first; if(!G.alive(c)) continue; // calc cost MFP([&](auto dfs,int v,int p,ll d)->void{ chmin(dp[v],-d+res); for(auto[u,w]:H[v]){ if(u==p) continue; if(!G.alive(u)) continue; dfs(u,v,d+w); } })(c,r,ch.second); // update cost MFP([&](auto dfs,int v,int p,ll d)->void{ chmin(res,d); for(auto[u,w]:H[v]){ if(u==p) continue; if(!G.alive(u)) continue; dfs(u,v,d+w); } })(c,r,ch.second); } chmin(dp[r],res); reverse(H[r].begin(),H[r].end()); } G.disable(r); for(int c:G.G[r]) if(G.alive(c)) que.emplace(G.build(c)[0]); } ll ans=0; for(ll x:dp) ans+=x; cout<<-ans<<endl; return 0; }
#line 1 "test/aoj/3142.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3142 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "tools/chminmax.cpp" #line 3 "tools/chminmax.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "tools/fixpoint.cpp" #line 3 "tools/fixpoint.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename F> struct FixPoint : F{ FixPoint(F&& f):F(forward<F>(f)){} template<typename... Args> decltype(auto) operator()(Args&&... args) const{ return F::operator()(*this,forward<Args>(args)...); } }; template<typename F> inline decltype(auto) MFP(F&& f){ return FixPoint<F>{forward<F>(f)}; } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "tree/centroid.cpp" #line 3 "tree/centroid.cpp" using namespace std; #endif //BEGIN CUT HERE struct Centroid{ vector<int> sz,dead; vector< vector<int> > G; Centroid(int n):sz(n,1),dead(n,0),G(n){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } int dfs(int v,int p){ sz[v]=1; for(int u:G[v]) if(u!=p and !dead[u]) sz[v]+=dfs(u,v); return sz[v]; } void find(int v,int p,int tmp,vector<int> &cs) { int ok=1; for (int u:G[v]){ if(u==p or dead[u]) continue; find(u,v,tmp,cs); ok&=(sz[u]<=tmp/2); } ok&=(tmp-sz[v]<=tmp/2); if(ok) cs.emplace_back(v); } vector<int> build(int r) { int tmp=dfs(r,-1); vector<int> cs; find(r,-1,tmp,cs); return cs; } const vector<int>& operator[](int k)const{return G[k];} void disable(int v){dead[v]=1;} void enable(int v){dead[v]=0;} int alive(int v){return !dead[v];} }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 10 "test/aoj/3142.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n; cin>>n; Centroid G(n); for(int i=1;i<n;i++){ int u,v; cin>>u>>v; u--;v--; G.add_edge(u,v); } vector<ll> as(n),bs(n); for(int i=0;i<n;i++) cin>>as[i]; for(int i=0;i<n;i++) cin>>bs[i]; using P = pair<int, ll>; vector<vector<P>> H(n); MFP([&](auto dfs,int v,int p)->ll{ ll res=as[v]-bs[v]; for(int u:G[v]){ if(u==p) continue; ll tmp=dfs(u,v); H[u].emplace_back(v,-tmp); H[v].emplace_back(u,+tmp); res+=tmp; } return res; })(0,-1); vector<ll> dp(n,0); queue<int> que; que.emplace(G.build(0)[0]); vector<ll> tmp(n); while(!que.empty()){ int r=que.front();que.pop(); for(int t=0;t<2;t++){ ll res=0; for(auto ch:H[r]){ int c=ch.first; if(!G.alive(c)) continue; // calc cost MFP([&](auto dfs,int v,int p,ll d)->void{ chmin(dp[v],-d+res); for(auto[u,w]:H[v]){ if(u==p) continue; if(!G.alive(u)) continue; dfs(u,v,d+w); } })(c,r,ch.second); // update cost MFP([&](auto dfs,int v,int p,ll d)->void{ chmin(res,d); for(auto[u,w]:H[v]){ if(u==p) continue; if(!G.alive(u)) continue; dfs(u,v,d+w); } })(c,r,ch.second); } chmin(dp[r],res); reverse(H[r].begin(),H[r].end()); } G.disable(r); for(int c:G.G[r]) if(G.alive(c)) que.emplace(G.build(c)[0]); } ll ans=0; for(ll x:dp) ans+=x; cout<<-ans<<endl; return 0; }