結果

問題 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,192 ms
コンパイル使用メモリ 210,004 KB
実行使用メモリ 30,784 KB
最終ジャッジ日時 2023-09-16 10:38:12
合計ジャッジ時間 11,949 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 305 ms
29,328 KB
testcase_04 AC 306 ms
29,328 KB
testcase_05 AC 270 ms
29,380 KB
testcase_06 AC 279 ms
29,308 KB
testcase_07 AC 281 ms
29,316 KB
testcase_08 AC 291 ms
29,320 KB
testcase_09 AC 292 ms
29,440 KB
testcase_10 AC 303 ms
29,404 KB
testcase_11 AC 301 ms
29,388 KB
testcase_12 AC 302 ms
29,512 KB
testcase_13 AC 251 ms
29,648 KB
testcase_14 AC 343 ms
29,552 KB
testcase_15 AC 359 ms
29,548 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 364 ms
29,688 KB
testcase_27 AC 357 ms
29,552 KB
testcase_28 AC 361 ms
29,548 KB
testcase_29 AC 249 ms
29,696 KB
testcase_30 AC 92 ms
14,180 KB
testcase_31 AC 45 ms
9,484 KB
testcase_32 AC 142 ms
18,660 KB
testcase_33 AC 106 ms
15,668 KB
testcase_34 AC 222 ms
24,724 KB
testcase_35 AC 145 ms
18,716 KB
testcase_36 AC 73 ms
12,816 KB
testcase_37 AC 81 ms
13,184 KB
testcase_38 AC 92 ms
14,828 KB
testcase_39 AC 177 ms
21,784 KB
testcase_40 AC 181 ms
30,152 KB
testcase_41 WA -
testcase_42 AC 183 ms
30,164 KB
testcase_43 AC 174 ms
30,292 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