带权图建树

/*
    问题描述：
    
*/

/*
    问题描述：
    
*/
#include<iostream>
#include<sstream>
#include<queue>
#include <bitset>
#include<algorithm>
#include<vector>
#include<string>
#define MAX  10010
using namespace std;
struct Node
{
    int knoop;//节点序号
    int weight;//权重
    Node(int knoop,int weight)
    {
        this->knoop = knoop;
        this->weight = weight;
    }
};
//存储图   新建树
vector<Node> chart[MAX],tree[MAX];
int vis[MAX] = {0};//存储是否被遍历过的
Node node(1,0);//标记从1出发  到达的最长路径的节点  和最长路径值
//以图的某个节点创建一颗树
void createTree(int strat);
void visChart(int start);
void visTree(int start);
int getNoVis(int n);
void getMaxValue(int start,int value);
int getSum(int n);
int main()
{
    freopen("in.txt","r",stdin);
    int n;
    cin >> n;
    for(int i = 1;i < n;i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        Node node1(x,z),node2(y,z);
        chart[x].push_back(node2);
        chart[y].push_back(node1);
    }
    createTree(1);
    //visTree(1);
    getMaxValue(1,0);
    //cout << node.knoop << " " << node.weight << endl;
    for(int i = 1;i <= n;i++)
    {
        tree[i].clear();
        vis[i] = 0;
    }
    
    createTree(4);
    //visTree(4);
    getMaxValue(node.knoop,0);
    cout << getSum(node.weight)+node.weight*10;
    //cout << node.knoop << " " << node.weight << endl;
}

int getSum(int n)
{
    if(n==1)
    return 1;
    return getSum(n-1)+n;
}
/*
从start节点开始遍历所有的相连节点
0.判断是否已经遍历
1.放入树中
2.标记已遍历
3.继续遍历相连节点
if 未被标记的孩子数为0退出
*/
void createTree(int start)
{
    if(getNoVis(start)==0)
    return ;
    vis[start] = 1; 
    int size = chart[start].size();
    for(int i = 0;i < size;i++)
    {
        if(vis[chart[start][i].knoop]==1)
        continue;
        vis[chart[start][i].knoop] = 1;
        tree[start].push_back(chart[start][i]);
        createTree(chart[start][i].knoop);
    }
}

//从某个点出发到达叶子节点的最大路径
/*
    步骤：
    出口到达叶子节点
    是否修改数据看到达叶子的节点的权重
    
    遍历所有的孩子节点
*/
void getMaxValue(int start,int value)
{
    int size = tree[start].size();
    if(size==0)
    {
        if(value>node.weight)
        {
            node.knoop = start;
            node.weight = value;
        }
    }
    for(int i = 0;i < size;i++)
    {
        getMaxValue(tree[start][i].knoop,value+tree[start][i].weight);
    }
}
int getNoVis(int n)
{
    int size = chart[n].size();
    int count = 0;
    for(int i = 0;i < size;i++)
    if(vis[chart[n][i].knoop]==0)
    count++;

    return count;
}
void visChart(int start)
{
    int M[MAX] = {0};
    queue<Node> q;
    q.push(Node(start,0));
    cout << start << endl;
    M[start] = 1;
    while(!q.empty())
    {
        //取出第一个
        Node temp = q.front();
        q.pop();
        int size = chart[temp.knoop].size();
        for(int i = 0;i < size;i++)
        {
            if(M[chart[temp.knoop][i].knoop]==1)
            continue;
            M[chart[temp.knoop][i].knoop] = 1;
            cout << chart[temp.knoop][i].knoop << endl;
            q.push(chart[temp.knoop][i]);
        }
    }
}
void visTree(int start)
{
    queue<Node> q;
    q.push(Node(start,0));
    cout << start << endl;
    while(!q.empty())
    {
        //取出第一个
        Node temp = q.front();
        q.pop();
        int size = tree[temp.knoop].size();
        for(int i = 0;i < size;i++)
        {
            cout << tree[temp.knoop][i].knoop << endl;
            q.push(tree[temp.knoop][i]);
        }
    }
}