結果

問題 No.386 貪欲な領主
ユーザー tails
提出日時 2016-07-02 00:19:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 976 bytes
コンパイル時間 1,616 ms
コンパイル使用メモリ 169,492 KB
実行使用メモリ 22,656 KB
最終ジャッジ日時 2024-10-12 19:34:06
合計ジャッジ時間 5,365 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 3 TLE * 1 -- * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

int n;
int ab[100000][2];
int u[100000];
int m;

list<int> lk[100000];
bool visited[100000];
int pr[100000];

int path0[100000];
int path1[100000];

void hoge(int i,int p){
	if(!visited[i]){
		visited[i]=true;
		pr[i]=p;
		for(list<int>::iterator t=lk[i].begin();t!=lk[i].end();++t){
			hoge(*t,i);
		}
	}
}

main(){
	cin >> n;
	for(int i=0;i<n-1;++i){
		cin >> ab[i][0] >> ab[i][1];
		lk[ab[i][0]].push_back(ab[i][1]);
		lk[ab[i][1]].push_back(ab[i][0]);
	}
	for(int i=0;i<n;++i){
		cin >> u[i];
	}

	hoge(0,-1);

	int sum=0;
	
	cin >> m;
	for(int i=0;i<m;++i){
		int a,b,c;
		cin >> a >> b >> c;
		int l0=0;
		for(int j=a;j>=0;j=pr[j]){
			path0[l0++]=j;
		}
		int l1=0;
		for(int j=b;j>=0;j=pr[j]){
			path1[l1++]=j;
		}
		while(l0>=0&&l1>=0&&path0[l0]==path1[l1]){
			--l0;
			--l1;
		}
		++l0;
		while(l0>=0){
			sum+=u[path0[l0--]]*c;
		}
		while(l1>=0){
			sum+=u[path1[l1--]]*c;
		}
	}
	cout << sum << endl;

	return 0;
}
0