cogs 944. [東方S3] 藤原妹红

二次联通门 : cogs 944. [東方S3] 藤原妹红

/*

    cogs 944. [東方S3] 藤原妹红

    最小生成树 + 树形dp

    首先对原图跑最下生成树

    后建出一棵树

    在树上进行dp

    先走到叶子节点, 顺便处理出距离

    最终回溯时更新答案

*/

#include <algorithm>

#include <cstdio>

#define INF 1e30

void read (int &now)

{

    register char word = getchar ();

    for (now = ; word < '' || word > ''; word = getchar ());

    for (; word >= '' && word <= ''; now = now *  + word - '', word = getchar ());

}

#define Max 300010

int N, M;

#define Online

struct Edge_Data

{

    int from;

    int to;

    double value;

    bool operator < (const Edge_Data &now) const

    {

        return this->value < now.value;

    }

};

double Max_dis = INF;

int Answer;

class Tree_Dp_Type

{

    private :

        int __to[Max], count[Max];

        double __value[Max];

        int __next[Max];

        int edge_list[Max];

        int Edge_Count;

        double dis[Max];

        double Sum;

    public :

        Tree_Dp_Type ()

        {

            Sum = ;

        }

        inline void Insert_edge (int from, int to, double value)

        {

            Edge_Count ++;

            __to[Edge_Count] = to;

            __next[Edge_Count] = edge_list[from];

            edge_list[from] = Edge_Count;

            Edge_Count ++;

            __to[Edge_Count] = from;

            __value[Edge_Count] = __value[Edge_Count - ] = value;

            __next[Edge_Count] = edge_list[to];

            edge_list[to] = Edge_Count;

            count[from] ++;

            count[to] ++;

            Sum += value;

        }

        double Dfs (int now, int father)

        {

            double avg = Sum / (double) count[now];

            double res = , __res = ;

            for (int i = edge_list[now]; i; i = __next[i])

            {

                if (__to[i] == father)

                     continue;

                dis[__to[i]] = __value[i] + Dfs (__to[i], now);

                res += (dis[__to[i]] - avg) * (dis[__to[i]] - avg);

                __res += dis[__to[i]];

            }

            res += (Sum - __res - avg) * (Sum - __res - avg);

            if (count[now] !=  && (res < Max_dis || (res == Max_dis && Answer > now)))

            {

                Answer = now;

                Max_dis = res;

            }

            return __res;

        }

};

Tree_Dp_Type Dp;

class Min_Out_Tree_Type

{

    private :

        int father[Max];

        int edge_list[Max];

        int Edge_Count;

        Edge_Data edge[Max * ];

    public :

        void Prepare (int Limit)

        {/*

            register int i;

            for (i = 1; i <= Limit; i += 3)

            {

                father[i] = i;

                father[i + 1] = i + 1;

                father[i + 2] = i + 2;

            }

            if (i > Limit)

                for (i -= 3; i > N; i ++)

                    father[i] = i;

        */

            for (register int i = ; i <= Limit; i ++)

                father[i] = i;

        }

        int Find (int x)

        {

            return father[x] == x ? x : father[x] = this->Find (father[x]);

        }

        inline void Insert_edge (int from, int to, double key)

        {

            Edge_Count ++;

            edge[Edge_Count].from = from;

            edge[Edge_Count].to = to;

            edge[Edge_Count].value = key;

        }

        void Get_Min_Value_Tree ()

        {

            std :: sort (edge + , edge + M + );

            int Count = ;

            for (register int i = , x, y; i <= M; i ++)

            {

                x = this->Find (edge[i].from);

                y = this->Find (edge[i].to);

                if (x != y)

                {

                    father[x] = y;

                    Count ++;

                    Dp.Insert_edge (edge[i].from, edge[i].to, edge[i].value);

                }

                if (Count == N - )

                    break;

            }

        }

};

Min_Out_Tree_Type Get_Tree;

int main (int argc, char *argv[])

{

#ifdef Online

    freopen ("mokou.in", "r", stdin);

    freopen ("mokou.out", "w", stdout);

#endif

    read (N);

    read (M);

    int x, y;

    double z;

    Get_Tree.Prepare (N);

    for (int i = ; i <= M; i ++)

    {

        read (x);

        read (y);

        scanf ("%lf", &z);

        Get_Tree.Insert_edge (x, y, z);

    }

    Get_Tree.Get_Min_Value_Tree ();

    Dp.Dfs (, );

    printf ("%d", Answer);

    return ;

}