結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2021-09-14 23:57:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 392 ms / 2,000 ms |
コード長 | 3,534 bytes |
コンパイル時間 | 2,950 ms |
コンパイル使用メモリ | 207,004 KB |
最終ジャッジ日時 | 2025-01-24 13:56:45 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(ll i=0;i<n;i++)#define repl(i,l,r) for(ll i=(l);i<(r);i++)#define per(i,n) for(ll i=(n)-1;i>=0;i--)#define perl(i,r,l) for(ll i=r-1;i>=l;i--)#define fi first#define se second#define pb push_back#define ins insert#define pqueue(x) priority_queue<x,vector<x>,greater<x>>#define all(x) (x).begin(),(x).end()#define CST(x) cout<<fixed<<setprecision(x)#define vtpl(x,y,z) vector<tuple<x,y,z>>#define rev(x) reverse(x);using ll=long long;using vl=vector<ll>;using vvl=vector<vector<ll>>;using pl=pair<ll,ll>;using vpl=vector<pl>;using vvpl=vector<vpl>;const ll MOD=1000000007;const ll MOD9=998244353;const int inf=1e9+10;const ll INF=4e18;const ll dy[9]={0,1,-1,0,1,1,-1,-1,0};const ll dx[9]={1,0,0,-1,1,-1,1,-1,0};template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}struct Edge {long long to;};using Graph = vector<vector<Edge>>;struct LCA {vector<vector<int>> parent; // parent[k][u]:= u の 2^k 先の親vector<int> dist; // root からの距離LCA(const Graph &G, int root = 0) { init(G, root); }void init(const Graph &G, int root = 0) {int V = G.size();int K = 1;while ((1 << K) < V) K++;parent.assign(K, vector<int>(V, -1));dist.assign(V, -1);dfs(G, root, -1, 0);for (int k = 0; k + 1 < K; k++) {for (int v = 0; v < V; v++) {if (parent[k][v] >= 0) {parent[k + 1][v] = parent[k][parent[k][v]];}}}}// 根からの距離と1つ先の頂点を求めるvoid dfs(const Graph &G, int v, int p, int d) {parent[0][v] = p;dist[v] = d;for (auto e : G[v]) {if (e.to != p) {dfs(G, e.to, v, d + 1);}}}int query(int u, int v) {if (dist[u] < dist[v]) swap(u, v); // u の方が深いとするint K = parent.size();// LCA までの距離を同じにするfor (int k = 0; k < K; k++) {if ((dist[u] - dist[v])&(1<<k) ){u = parent[k][u];}}// 二分探索で LCA を求めるif (u == v) return u;for (int k = K - 1; k >= 0; k--) {if (parent[k][u] != parent[k][v]) {u = parent[k][u];v = parent[k][v];}}return parent[0][u];}int length(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; }bool is_in(int u, int v, int a) { return length(u, a) + length(a, v) == length(u, v); }};vector<vector<Edge>> g(100010);vl dp(100010);vl lc(100010);ll dfs(ll v,ll par=-1){for(auto p:g[v]){if(p.to==par)continue;dp[v]+=dfs(p.to,v);}return dp[v]-lc[v]*2;}int main(){ll n;cin >> n;rep(i,n-1){ll a,b;cin >> a >> b;g[a].push_back({b});g[b].push_back({a});}LCA lca(g);vl x(n);rep(i,n)cin >> x[i];ll q;cin >> q;while(q--){ll a,b,c;cin >> a >> b >> c;ll l=lca.query(a,b);lc[l]+=c;dp[a]+=c;dp[b]+=c;}dfs(0);ll ans=0;rep(i,n){ans+=x[i]*(dp[i]-lc[i]);}cout << ans << endl;}