結果

問題 No.1333 Squared Sum
ユーザー 👑 potato167potato167
提出日時 2022-02-25 17:06:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,765 bytes
コンパイル時間 2,078 ms
コンパイル使用メモリ 212,364 KB
実行使用メモリ 30,424 KB
最終ジャッジ日時 2024-07-03 11:37:05
合計ジャッジ時間 10,072 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 238 ms
29,588 KB
testcase_04 AC 234 ms
29,716 KB
testcase_05 AC 244 ms
29,716 KB
testcase_06 AC 245 ms
29,688 KB
testcase_07 AC 250 ms
29,588 KB
testcase_08 AC 235 ms
29,584 KB
testcase_09 AC 250 ms
29,716 KB
testcase_10 AC 235 ms
29,712 KB
testcase_11 AC 241 ms
29,712 KB
testcase_12 AC 248 ms
29,712 KB
testcase_13 AC 202 ms
29,948 KB
testcase_14 AC 262 ms
29,820 KB
testcase_15 AC 255 ms
29,940 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 267 ms
29,944 KB
testcase_27 AC 316 ms
29,944 KB
testcase_28 AC 270 ms
29,944 KB
testcase_29 AC 201 ms
29,820 KB
testcase_30 AC 75 ms
14,476 KB
testcase_31 AC 39 ms
9,600 KB
testcase_32 AC 123 ms
19,084 KB
testcase_33 AC 86 ms
15,948 KB
testcase_34 AC 171 ms
24,876 KB
testcase_35 AC 112 ms
19,000 KB
testcase_36 AC 61 ms
13,236 KB
testcase_37 AC 65 ms
13,592 KB
testcase_38 AC 79 ms
14,932 KB
testcase_39 AC 156 ms
22,068 KB
testcase_40 AC 157 ms
30,296 KB
testcase_41 WA -
testcase_42 AC 148 ms
30,184 KB
testcase_43 AC 150 ms
30,424 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);
	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