結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2021-02-05 05:51:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 409 ms / 2,000 ms |
コード長 | 3,516 bytes |
コンパイル時間 | 2,112 ms |
コンパイル使用メモリ | 201,864 KB |
最終ジャッジ日時 | 2025-01-18 11:40:48 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); ++i)#define drep(i,n) for(int i = (n)-1; i >= 0; --i)#define srep(i,s,t) for (int i = s; i < t; ++i)using namespace std;typedef long long int ll;typedef pair<int,int> P;#define yn {puts("YES");}else{puts("NO");}struct edge{ int to, cost; };#define MAX_N 200005#define MAX_LOG_N 25vector<edge> pre_G[MAX_N];vector<edge> G[MAX_N];int par_[MAX_N];int parent[MAX_LOG_N][MAX_N];int flag_netsukigi[MAX_N];int depth[MAX_N];int root;void make_netsukigi(int r){root = r;queue<int> que;que.push(r);flag_netsukigi[r] = 1;par_[r] = -1;depth[r] = 0;while(que.size() > 0){int x = que.front();que.pop();flag_netsukigi[x] = 1;rep(i,pre_G[x].size()){if(flag_netsukigi[pre_G[x][i].to] == 0){par_[pre_G[x][i].to] = x;depth[pre_G[x][i].to] = depth[x] + 1;G[x].push_back(pre_G[x][i]);que.push(pre_G[x][i].to);}}}}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].to != p) dfs(G[v][i].to, v, d + 1);}}void init(int V){dfs(root, -1, 0);for(int k = 0; k + 1 < MAX_LOG_N; k++){for(int v = 0; v < V; v++){if(parent[k][v] < 0) parent[k+1][v] = -1;else parent[k+1][v] = parent[k][parent[k][v]];}}}int lca(int u, int v){if(depth[u] > depth[v])swap(u, v);for(int k = 0; k < MAX_LOG_N; k++){if((depth[v] - depth[u]) >> k & 1){v = parent[k][v];}}if(u == v)return u;for(int k = MAX_LOG_N - 1; k >= 0; k--){if(parent[k][u] != parent[k][v]){u = parent[k][u];v = parent[k][v];}}return parent[0][u];}int dist[MAX_N];void init_dist(int r){dist[r] = 0;queue<int> que;que.push(r);while(que.size() > 0){int x = que.front();que.pop();for(int i = 0; i < G[x].size(); i++){int y = G[x][i].to;dist[y] = dist[x] + G[x][i].cost;que.push(y);}}}int calcLength(int x, int y){int w = lca(x, y);int m = dist[x] - dist[w] + dist[y] - dist[w];return m;}int main() {int n;cin >> n;int a[n-1], b[n-1];rep(i,n-1){cin >> a[i] >> b[i];// a[i]--; b[i]--;edge e;e.to = b[i]; e.cost = 1;pre_G[a[i]].push_back(e);e.to = a[i];pre_G[b[i]].push_back(e);}make_netsukigi(0);init(n);init_dist(0);ll u[n] = {};rep(i,n) cin >> u[i];ll plus[n] = {}, minus[n] = {};int q;cin >> q;rep(_,q){int s, t, c;cin >> s >> t >> c;// s--; t--;int l = lca(s,t);plus[s] += c;plus[t] += c;minus[l] += c;}int sons[n] = {};queue<int> que;rep(i,n){sons[i] = G[i].size();if(sons[i] == 0) que.push(i);}ll ans = 0;ll dp[n] = {};while(que.size()){int x = que.front();que.pop();dp[x] += plus[x];dp[x] -= minus[x];ans += dp[x] * u[x];dp[x] -= minus[x];if(x == 0) continue;int y = par_[x];dp[y] += dp[x];sons[y]--;if(sons[y] == 0) que.push(y);}cout << ans << endl;return 0;}