#190719 (C++14) No.386 貪欲な領主

• 問題: No.386 貪欲な領主
• ユーザー: autumn-eel
• 提出日時: 2017-07-22 16:17:07
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 181 ms / 2,000 ms
• コード長: 1,054 bytes
• コンパイル時間: 1,537 ms
• コンパイル使用メモリ: 171,100 KB
• 実行使用メモリ: 22,528 KB
• 最終ジャッジ日時: 2024-10-09 09:56:25
• 合計ジャッジ時間: 3,996 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 6,144 KB
testcase_01	AC	4 ms; 6,144 KB
testcase_02	AC	4 ms; 6,016 KB
testcase_03	AC	4 ms; 6,144 KB
testcase_04	AC	181 ms; 22,528 KB
testcase_05	AC	143 ms; 18,048 KB
testcase_06	AC	145 ms; 17,920 KB
testcase_07	AC	5 ms; 6,144 KB
testcase_08	AC	21 ms; 7,168 KB
testcase_09	AC	6 ms; 6,272 KB
testcase_10	AC	4 ms; 6,016 KB
testcase_11	AC	4 ms; 6,144 KB
testcase_12	AC	5 ms; 6,144 KB
testcase_13	AC	7 ms; 6,528 KB
testcase_14	AC	143 ms; 17,920 KB
testcase_15	AC	166 ms; 22,404 KB

ソースコード

#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

vector<int>E[100000];
int par[18][100000],depth[100000],u[100000];
ll sum[100000];

void dfs(int v,int p,int d){
	if(p==-1)sum[v]=u[v];
	else sum[v]=sum[p]+u[v];
	par[0][v]=p;depth[v]=d;
	for(int u:E[v]){
		if(u!=p)dfs(u,v,d+1);
	}
}
int lca(int u,int v){
	if(depth[u]>depth[v])swap(u,v);
	rep(i,18){
		if((depth[v]-depth[u])>>i&1)v=par[i][v];
	}
	if(u==v)return u;
	for(int i=17;i>=0;i--){
		if(par[i][u]!=par[i][v]){
			u=par[i][u];
			v=par[i][v];
		}
	}
	return par[0][u];
}
int main(){
	int n;scanf("%d",&n);
	rep(i,n-1){
		int a,b;scanf("%d%d",&a,&b);
		E[a].push_back(b);E[b].push_back(a);
	}
	rep(i,n)scanf("%d",&u[i]);
	dfs(0,-1,0);
	for(int i=1;i<18;i++)rep(j,n){
		if(par[i-1][j]==-1)par[i][j]=-1;
		else par[i][j]=par[i-1][par[i-1][j]];
	}
	int m;scanf("%d",&m);
	ll ans=0;
	rep(i,m){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		int p=lca(a,b);
		ans+=(sum[a]+sum[b]-(par[0][p]==-1?0:sum[par[0][p]])-sum[p])*c;
	}
	printf("%lld\n",ans);
}