結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2020-05-05 17:35:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 173 ms / 3,000 ms |
コード長 | 806 bytes |
コンパイル時間 | 5,039 ms |
コンパイル使用メモリ | 199,284 KB |
最終ジャッジ日時 | 2025-01-10 06:53:14 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:37:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 37 | scanf("%d",&n); | ~~~~~^~~~~~~~~ main.cpp:40:33: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 40 | int u,v,c; scanf("%d%d%d",&u,&v,&c); u--; v--; | ~~~~~^~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(n);i++)using namespace std;using lint=long long;template<class T> struct edge{int to;T wt;edge(int to,const T& wt):to(to),wt(wt){}};template<class T> using weighted_graph=vector<vector<edge<T>>>;template<class T>void add_edge(weighted_graph<T>& G,int u,int v,const T& wt){G[u].emplace_back(v,wt);G[v].emplace_back(u,wt);}int n;weighted_graph<int> T;vector<int> sz;lint dfs(int u,int p){sz[u]=1;lint res=0;for(auto e:T[u]) if(e.to!=p) {int v=e.to;res+=dfs(v,u)+2LL*e.wt*sz[v]*(n-sz[v]);sz[u]+=sz[v];}return res;}int main(){scanf("%d",&n);T.resize(n);rep(i,n-1){int u,v,c; scanf("%d%d%d",&u,&v,&c); u--; v--;add_edge(T,u,v,c);}sz.resize(n);printf("%lld\n",dfs(0,-1));return 0;}