結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-08-07 12:52:26 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 326 ms / 2,000 ms |
コード長 | 1,894 bytes |
コンパイル時間 | 855 ms |
コンパイル使用メモリ | 83,128 KB |
実行使用メモリ | 41,188 KB |
最終ジャッジ日時 | 2024-11-07 07:14:42 |
合計ジャッジ時間 | 3,999 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <algorithm>#include <cstdio>#include <cstdlib>#include <cctype>#include <cmath>#include <iostream>#include <queue>#include <list>#include <stack>#include <map>#include <numeric>#include <set>#include <sstream>#include <string>#include <vector>using namespace std;#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)#define rep(i,n) REP(i,0,n)#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)#define ALLOF(c) (c).begin(), (c).end()typedef long long ll;int N;vector<int> G[100005];int parent[64][100005];int depth[100005];int dp[100005];int weight[100005];void dfs(int v, int p, int d){parent[0][v] = p;depth[v] = d;dp[v] = (p!=-1?dp[p]:0) + weight[v];for(int i=0; i<G[v].size(); i++){if(G[v][i] != p) dfs(G[v][i], v, d+1);}}void init(int root){dfs(root, -1, 0);for(int k=0; k+1<64; k++){for(int v=0; v<N+1; 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<64; k++){if((depth[v] - depth[u]) >> k & 1){v = parent[k][v];}}if(u==v) return u;for(int k=64-1; k>=0; k--){if(parent[k][u] != parent[k][v]){u = parent[k][u];v = parent[k][v];}}return parent[0][u];}int main(){ios::sync_with_stdio(false);cin >> N;rep(i,N-1){int a, b;cin >> a >> b;G[a].push_back(b);G[b].push_back(a);}rep(i,N){cin >> weight[i];}dp[0] = weight[0];init(0);int M;cin >> M;ll ret = 0;rep(i,M){int a, b, c;cin >> a >> b >> c;int l = lca(a, b);//cout << " " << dp[a] << " " << dp[b] << " " << dp[l] << " " << weight[l] << endl;ret += (dp[a] + dp[b] - 2LL*dp[l] + weight[l]) * (ll)c;}cout << ret << endl;return 0;}