結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2021-10-27 01:46:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 5,558 bytes |
コンパイル時間 | 2,176 ms |
コンパイル使用メモリ | 183,164 KB |
実行使用メモリ | 26,768 KB |
最終ジャッジ日時 | 2024-10-06 12:18:51 |
合計ジャッジ時間 | 4,611 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>#define all(v) v.begin(), v.end()#define rall(v) v.rbegin(), v.rend()#define rep(i,n) for(int i=0;i<(int)(n);i++)#define drep(i,j,n) for(int i=0;i<(int)(n-1);i++)for(int j=i+1;j<(int)(n);j++)#define trep(i,j,k,n) for(int i=0;i<(int)(n-2);i++)for(int j=i+1;j<(int)(n-1);j++)for(int k=j+1;k<(int)(n);k++)#define codefor int test;scanf("%d",&test);while(test--)#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)#define yes(ans) if(ans)printf("yes\n");else printf("no\n")#define Yes(ans) if(ans)printf("Yes\n");else printf("No\n")#define YES(ans) if(ans)printf("YES\n");else printf("NO\n")#define popcount(v) __builtin_popcount(v)#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))#define vector3d(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))using namespace std;using ll = long long;template<class T> using rpriority_queue = priority_queue<T, vector<T>, greater<T>>;const int MOD=1000000007;const int MOD2=998244353;const int INF=1<<30;const ll INF2=1LL<<60;void scan(int& a){scanf("%d",&a);}void scan(long long& a){scanf("%lld",&a);}template<class T,class L>void scan(pair<T, L>& p){scan(p.first);scan(p.second);}template<class T,class U,class V>void scan(tuple<T,U,V>& p){scan(get<0>(p));scan(get<1>(p));scan(get<2>(p));}template<class T> void scan(T& a){cin>>a;}template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}void in(){}template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}void print(const int& a){printf("%d",a);}void print(const long long& a){printf("%lld",a);}void print(const double& a){printf("%.15lf",a);}template<class T,class L>void print(const pair<T, L>& p){print(p.first);putchar(' ');print(p.second);}template<class T> void print(const T& a){cout<<a;}template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}void out(){putchar('\n');}template<class T> void out(const T& t){print(t);putchar('\n');}template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}template<class T> void dprint(const T& a){cerr<<a;}template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}void debug(){cerr<<endl;}template<class T> void debug(const T& t){dprint(t);cerr<<endl;}template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }ll modinv(ll a, ll m) {ll b = m, u = 1, v = 0;while (b) {ll t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;returnu;}ll updivide(ll a,ll b){return (a+b-1)/b;}template<class T> void chmax(T &a,const T b){if(b>a)a=b;}template<class T> void chmin(T &a,const T b){if(b<a)a=b;}struct LCA_tree{int _n,MAX_LOG_V,root;vector<vector<int>> g;vector<vector<int>> parent;vector<int> depth;const vector<int>& operator[](int i) const { return g[i]; }vector<int>& operator[](int i) { return g[i]; }LCA_tree() : _n(0) {}LCA_tree(int n) : _n(n), g(n),depth(n) {MAX_LOG_V=1;while(_n>>MAX_LOG_V)MAX_LOG_V++;parent.resize(MAX_LOG_V,vector<int>(_n));}void merge(int u,int v){g[u].push_back(v);g[v].push_back(u);}void dfs(int v,int p,int d){parent[0][v]=p;depth[v]=d;for(int i=0;i<g[v].size();i++){if(g[v][i]!=p)dfs(g[v][i],v,d+1);}}void init(int r){root=r;dfs(root,-1,0);for(int j=0;j+1<MAX_LOG_V;j++){for(int i=0;i<_n;i++){if(parent[j][i]<0)parent[j+1][i]=-1;else parent[j+1][i]=parent[j][parent[j][i]];}}}int lca(int u,int v){if(depth[u]>depth[v])swap(u,v);for(int i=0;i<MAX_LOG_V;i++){if((depth[v]-depth[u])>>i&1)v=parent[i][v];}if(u==v)return u;for(int i=MAX_LOG_V-1;i>=0;i--){if(parent[i][u]!=parent[i][v]){u=parent[i][u];v=parent[i][v];}}return parent[0][u];}//パスの辺数int dist(int u,int v){int lcav=lca(u,v);if(lcav==-1)return depth[u]+depth[v];return depth[u]+depth[v]-2*depth[lcav];}//頂点wが頂点u,vのパス上に存在するかint on_path(int u,int v,int w){return (dist(u,w)+dist(v,w)==dist(u,v));}};int main(){INT(n);LCA_tree g(n);int u,v,c;ll ans=0,sumv=0;rep(i,n-1){in(u,v);g.merge(u,v);}vector<ll> cnt(n,0),a(n);in(a);g.init(0);INT(m);rep(i,m){in(u,v,c);cnt[u]+=c;cnt[v]+=c;int lcav=g.lca(u,v);cnt[lcav]-=2*c;ans+=c*a[lcav];}function<void(int,int)> dfs=[&](int v,int p){sumv+=a[v];ans+=sumv*cnt[v];for(auto u:g[v]){if(u==p)continue;dfs(u,v);}sumv-=a[v];};dfs(0,-1);out(ans);}