結果

問題 No.386 貪欲な領主
ユーザー imulan
提出日時 2018-03-15 02:47:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 223 ms / 2,000 ms
コード長 2,615 bytes
コンパイル時間 1,728 ms
コンパイル使用メモリ 170,456 KB
実行使用メモリ 24,064 KB
最終ジャッジ日時 2024-11-30 12:13:28
合計ジャッジ時間 3,958 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
//
const int MAX_V = 100000;
//(log(MAX_V))
const int MAX_LOG_V = 18;
//
vector<int> G[MAX_V];
//
int root = 0;
//2^k辿(,-1)
int parent[MAX_LOG_V][MAX_V];
//
int depth[MAX_V];
//vpd
void lca_dfs(int v, int p, int d){
parent[0][v]=p;
depth[v]=d;
rep(i,G[v].size()){
if(G[v][i]!=p){ //
lca_dfs(G[v][i], v, d+1);
}
}
}
//
void lca_init(int V){
//parent[0]depth
lca_dfs(root, -1, 0);
//parent
for(int k=0; k+1<MAX_LOG_V; ++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]];
}
}
}
//uvLCA
int lca(int u, int v){
//uv辿
if(depth[u] > depth[v]) swap(u,v);
for(int k=0; k<MAX_LOG_V; ++k){
if((depth[v]-depth[u])>>k & 1) v = parent[k][v];
}
if(u==v) return u;
//LCA
for(int k=MAX_LOG_V-1; k>=0; --k){
if(parent[k][u] != parent[k][v]){
u=parent[k][u];
v=parent[k][v];
}
}
return parent[0][u];
}
int par[MAX_V]={};
ll dp[MAX_V]={};
void dfs(int cur){
for(int nx:G[cur])if(nx != par[cur]){
par[nx] = cur;
dp[nx] += dp[cur];
dfs(nx);
}
}
int main(){
int n;
scanf(" %d", &n);
rep(i,n-1){
int a,b;
scanf(" %d %d", &a, &b);
G[a].pb(b);
G[b].pb(a);
}
lca_init(n);
vector<int> u(n);
rep(i,n){
scanf(" %d", &u[i]);
dp[i] += u[i];
}
par[0] = -1;
dfs(0);
int m;
scanf(" %d", &m);
ll ans = 0;
while(m--){
int a,b,c;
scanf(" %d %d %d", &a, &b, &c);
int x = lca(a,b);
ans += (dp[a]+dp[b]-2*dp[x]+u[x])*c;
}
printf("%lld\n", ans);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0