結果

問題 No.872 All Tree Path
コンテスト
ユーザー kafuka97
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0