結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2016-07-02 00:16:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 199 ms / 2,000 ms |
コード長 | 2,495 bytes |
コンパイル時間 | 1,645 ms |
コンパイル使用メモリ | 170,712 KB |
実行使用メモリ | 33,664 KB |
最終ジャッジ日時 | 2024-10-12 19:19:37 |
合計ジャッジ時間 | 3,857 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<ll> vll;const int MAX = 100001, LG = 18;int N, U[MAX], anc[LG][MAX], dep[MAX], par[MAX];ll cost[LG][MAX];vi G[MAX];void dfs(int v, int p, int d){dep[v] = d;par[v] = p;for(int to : G[v])if(to != p)dfs(to, v, d + 1);}void init(){MEM(anc, 0);MEM(dep, 0);MEM(par, 0);MEM(cost, 0);rep(i, N)G[i].clear();rep(i, N - 1){int a, b;scanf("%d%d", &a, &b);G[a].push_back(b);G[b].push_back(a);}rep(i, N)scanf("%d", &U[i]);// lcadfs(0, 0, 0);rep(i, N){anc[0][i] = par[i];if(i)cost[0][i] = U[par[i]];}rep(i, LG - 1)rep(v, N){anc[i + 1][v] = anc[i][anc[i][v]];cost[i + 1][v] = cost[i][v] + cost[i][anc[i][v]];}}ll solve(int A, int B, int C){//debug(A);//debug(B);if(dep[A] < dep[B])swap(A, B);ll res = U[A] + U[B];int u = A, v = B;int dist = dep[u] - dep[v];for(int i = 0; i < LG; ++i)if(dist >> i & 1){res += cost[i][u];u = anc[i][u];}if(u == v){if(u == B)res -= U[B];return res*C;} else{for(int i = LG - 1; i >= 0; --i){if(anc[i][u] != anc[i][v]){res += cost[i][u];res += cost[i][v];u = anc[i][u];v = anc[i][v];}}int lca = anc[0][u];res += U[lca];/*debug(res);debug(A);debug(B);debug(u);debug(v);if(u != lca && u != A)res += U[u];if(v != lca && v != B)res += U[v];*/return res*C;}}int main(){while(cin >> N){init();int M;cin >> M;ll ans = 0;while(M--){int A, B, C;scanf("%d%d%d", &A, &B, &C);// debug(solve(A, B, C));ans += solve(A, B, C);}cout << ans << endl;}}