結果

問題 No.1333 Squared Sum
ユーザー 👑 potato167potato167
提出日時 2022-02-25 17:07:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,812 bytes
コンパイル時間 2,061 ms
コンパイル使用メモリ 211,604 KB
実行使用メモリ 30,548 KB
最終ジャッジ日時 2023-09-16 10:39:22
合計ジャッジ時間 9,731 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 216 ms
29,364 KB
testcase_04 AC 215 ms
29,396 KB
testcase_05 AC 218 ms
29,300 KB
testcase_06 AC 212 ms
29,464 KB
testcase_07 AC 217 ms
29,296 KB
testcase_08 AC 212 ms
29,340 KB
testcase_09 AC 214 ms
29,320 KB
testcase_10 AC 212 ms
29,524 KB
testcase_11 AC 213 ms
29,392 KB
testcase_12 AC 216 ms
29,336 KB
testcase_13 AC 187 ms
29,572 KB
testcase_14 AC 230 ms
29,524 KB
testcase_15 AC 233 ms
29,596 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 233 ms
29,736 KB
testcase_27 AC 225 ms
29,692 KB
testcase_28 AC 227 ms
29,692 KB
testcase_29 AC 182 ms
29,584 KB
testcase_30 AC 77 ms
14,196 KB
testcase_31 AC 41 ms
9,408 KB
testcase_32 AC 115 ms
18,800 KB
testcase_33 AC 88 ms
15,624 KB
testcase_34 AC 164 ms
24,756 KB
testcase_35 AC 119 ms
18,860 KB
testcase_36 AC 66 ms
12,820 KB
testcase_37 AC 68 ms
13,364 KB
testcase_38 AC 80 ms
14,712 KB
testcase_39 AC 140 ms
21,936 KB
testcase_40 AC 154 ms
30,236 KB
testcase_41 WA -
testcase_42 AC 155 ms
30,180 KB
testcase_43 AC 151 ms
30,252 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using std::cout;
using std::cin;
using std::endl;
using ll=long long;
ll mod=1e9+7;
#define rep(i,a) for (ll i=0;i<a;i++)


namespace po167{
struct UFtree
{
	std::vector<int> wei;
	int component;
	UFtree(int n):par(n),wei(n),component(n){
		for(int i=0;i<n;i++){
			wei[i]=1,par[i]=i;
		}
	}
	void intialize(){
		for(int i=0;i<(int) par.size();i++){
			wei[i]=1,par[i]=i;
		}
		component=(int)par.size();
	}
	//根っこを返す
	int root(int a){
		if(a==par[a]) return a;
		return par[a]=root(par[a]);
	}
	//trueなら1,falseなら0
	int same(int a,int b){
		if(root(a)==root(b)) return 1;
		else return 0;
	}
	//a,bが違う根っこの元なら結合する,結合したらtrueを返す
	bool unite(int a,int b){
		a=root(a),b=root(b);
		if(a==b) return false;
		if(wei[a]<wei[b]) std::swap(a,b);
		par[b]=a;
		wei[a]+=wei[b];
		component--;
		return true;
	}
	private:
	std::vector<int> par;
};
}
using po167::UFtree;

struct edge{
	int to;
	ll len;
};

const int MAX_N=2e5;
const int MAX_C=1e9;

//おちこんだりもしたけれど、私はげんきです。
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	ll N;
	cin>>N;
	assert(1<=N&&N<=MAX_N);
	if(N==1){
	    cout<<"0\n";
	    return 0;
	}
	UFtree tree(N);
	vector<vector<edge>> G(N);

	rep(i,N-1){
		int a,b;ll c;
		cin>>a>>b>>c;
		assert(1<=c&&c<=MAX_C);
		a--,b--;
		assert(tree.unite(a,b));
		G[a].push_back({b,c});
		G[b].push_back({a,c});
	}

	ll ans=0;
	vector<ll> subtree_size(N,1);
	vector<edge> parent(N,{-1,-1});
	vector<ll> order={0};
	vector<ll> lower_dist_sum(N);
	vector<ll> upper_dist_sum(N);

	parent[0]={-2,-2};
	rep(i,N){
		int var=order[i];
		for(auto e:G[var]){
			if(parent[e.to].to==-1){
				parent[e.to]={var,e.len};
				order.push_back(e.to);
			}
		}
	}
	for(int i=N-1;i>=0;i--){
		int var=order[i];
		for(auto e:G[var]){
			if(e.to!=parent[var].to){
				subtree_size[var]+=subtree_size[e.to];
				lower_dist_sum[var]+=(subtree_size[e.to]*e.len)%mod;
				lower_dist_sum[var]+=lower_dist_sum[e.to];
				lower_dist_sum[var]%=mod;
			}
		}
	}

	rep(i,N){
		int var=order[i];
		for(auto e:G[var]){
			if(e.to==parent[var].to) continue;
			ll tmp_lower=(lower_dist_sum[e.to]+(subtree_size[e.to]*e.len)%mod)%mod;
			upper_dist_sum[e.to]=(upper_dist_sum[var]+lower_dist_sum[var]-tmp_lower)%mod;
			ll ans_sub=(upper_dist_sum[e.to]*subtree_size[e.to]);
			ans_sub+=(tmp_lower*(N-subtree_size[e.to]))%mod;
			ans_sub=((ans_sub%mod)*e.len)%mod;
			//cout<<ans_sub<<endl<<endl;
			ans+=ans_sub;
			ans%=mod;
			upper_dist_sum[e.to]+=(e.len*(N-subtree_size[e.to]))%mod;
			upper_dist_sum[e.to]%=mod;
		}
	}

	/*rep(i,N){
		cout<<upper_dist_sum[i]<<" "<<lower_dist_sum[i]<<" "<<subtree_size[i]<<endl;
		cout<<parent[i].to<<" "<<parent[i].len<<endl;
	}*/
	cout<<ans<<endl;
}
0