結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:09:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 177 ms / 3,000 ms |
コード長 | 3,162 bytes |
コンパイル時間 | 1,894 ms |
コンパイル使用メモリ | 171,228 KB |
実行使用メモリ | 43,424 KB |
最終ジャッジ日時 | 2024-11-21 23:50:46 |
合計ジャッジ時間 | 4,427 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef int64_t i64;typedef uint64_t ui64;class graph{public:struct adj{int index;int start;int to;i64 cost;};int nd;int eg;vector<adj> *node;vector<adj> edge;graph(int n,int m){nd=n;eg=m;node=new vector<adj>[nd]{};edge={};}void add_dir(int i,int s,int t,i64 c){node[s].push_back({i,s,t,c});edge.push_back({i,s,t,c});}void add_undir(int i,int s,int t,i64 c){node[s].push_back({i,s,t,c});node[t].push_back({i,t,s,c});edge.push_back({i,s,t,c});}void refr(void){for(int i=0;i<nd;i++) vector<adj>().swap(node[i]);delete[] node;vector<adj>().swap(edge);}bool IsLink(void);void DFS(int r,int *&p);void DFS_sub(int r,int *&p,bool *&vst);bool IsPlus(void);void BellmanFord(int s,i64 *&d);void Dijkstra(int s,i64 *&d);void BFS(int s,i64 *&d);void WarshallFloyd_dir(i64 **&d);void WarshallFloyd_undir(i64 **&d);i64 WMST_dir(int r);i64 WMST_undir(void);void Edmonds(int r,vector<adj> &p);void Kruscal(vector<adj> &p);void Prim(vector<adj> &p);void Artic(vector<int> &p);void Artic_sub(int r,int &k,int par,vector<int> &p,int *&ord,int *&low,bool *&vst);void Bridge(vector<adj> &p);void Bridge_sub(int r,int &k,int par,vector<adj> &p,int *&ord,int *&low,bool *&vst);void SCC(int *&c);void SCC_sub1(int r,vector<int> &vs,bool *&vst);void SCC_sub2(int r,int k,int *&c,bool *&vst,graph &rg);bool IsDAG(void);bool IsDAG_sub(int r,int &k,int *&l,int *&vst);void TopolSort(int *&l);void TopolSort_sub(int r,int &k,int *&l,bool *&vst);i64 Diameter(void);void Height(i64 *&h);void DFSTree(int s,vector<adj> &es);void DFSTree_sub(int r,vector<adj> &es,bool *&vst);void Cumul(int s,i64 *&d);void func(int r,int *&p,i64 *&es);void func_sub(int r,int *&p,i64 *&es,bool *&vst);};void graph::DFS(int r,int *&p){bool *vst=new bool[nd]{};DFS_sub(r,p,vst);delete[] vst;}void graph::DFS_sub(int r,int *&p,bool *&vst){vst[r]=1;int c=0;for(const auto &i:node[r]){if(!vst[i.to]) DFS_sub(i.to,p,vst);c+=p[i.to];}p[r]=c+1;}void graph::func(int r,int *&p,i64 *&es){bool *vst=new bool[nd]{};func_sub(r,p,es,vst);delete[] vst;}void graph::func_sub(int r,int *&p,i64 *&es,bool *&vst){vst[r]=1;for(const auto &i:node[r]){if(vst[i.to]) continue;es[i.index]=(i64)p[i.to]*((i64)nd-p[i.to])*2;func_sub(i.to,p,es,vst);}}int main(void){int n;scanf("%i",&n);graph g(n,n-1);int s,t;i64 w;for(int i=0;i<n-1;i++){scanf("%i%i%lli",&s,&t,&w);s--;t--;g.add_undir(i,s,t,w);}int *p=new int[n]{};g.DFS(0,p);i64 *es=new i64[n-1]{};g.func(0,p,es);i64 ans=0;for(int i=0;i<n-1;i++){ans+=es[i]*g.edge[i].cost;}printf("%lli\n",ans);return 0;}