题目地址

这就是一道搜索题目 不是标签为什么有动态规划
N点N-1条边 这就是一个树
搜索从根节点出发 做深度优先搜索
搜索的时候计算每个节点的权重
然后回溯的时候根据子节点的权重 计算需要调整的次数
并把该节点的权重调整为子节点权重的最大值

注意用long long保存结果

#include <stdio.h>

//图的边的结构体(也可以用来表示树)
struct LinkList
{
    //节点编号
    int index;
    //边的权重
    int value;
    //所有连接节点的边 包括根节点
    LinkList* next;
    LinkList* pre;
};

void deleteLinkList(LinkList* l)
{
    LinkList* next=l;
    while (next!=NULL)
    {
        LinkList* now=next->next;
        delete next;
        next=now;
    }
}

void addLinkList(LinkList** ev,int index,LinkList* l)
{
    if(ev[index]==NULL)
    {
        l->next=NULL;
        l->pre=NULL;
        ev[index]=l;
    }
    else{
        l->next=ev[index];
        l->pre=NULL;
        ev[index]->pre=l;
        ev[index]=l;
    }
}

int main(){
    int n,s;
    scanf("%d %d",&n,&s);
    s--;
    //储存节点分数
    int* input=new int[n];
    //记录树所有顶点
    LinkList** ev=new LinkList*[n];
    //DFS的时候记录遍历到了哪条边
    LinkList** stackList=new LinkList*[n];
    //DFS时候记录该节点是否已经完成计算 
    int* isUse=new int[n];

    int i;
    for(i=0;i<n;i++)
    {
        input[i]=0;
        ev[i]=NULL;
        stackList[i]=NULL;
        isUse[i]=0;
    }

    int tmp1,tmp2,tmp3;
    for(i=0;i<n-1;i++)
    {
        scanf("%d %d %d",&tmp1,&tmp2,&tmp3);
        tmp1--;
        tmp2--;

        //添加双向边
        LinkList* l=new LinkList;
        l->index=tmp2;
        l->value=tmp3;
        addLinkList(ev,tmp1,l);

        l=new LinkList;
        l->index=tmp1;
        l->value=tmp3;
        addLinkList(ev,tmp2,l);
    }

    long long resultValue=0;

    
    int** stack=new int*[n];
    
    //把s节点当成根节点 入栈开始DP
    int len=0;
    //0存储当前节点 1存储当前节点的根节点
    stack[len]=new int[2];
    stack[len][0]=s;
    stack[len][1]=-1;
    len++;
    while (len>0)
    {
        LinkList* l;
        //根节点
        int rootIndex=stack[len-1][1];
        //当前节点
        int index=stack[len-1][0];

        //如果已经开始遍历 从上次遍历的边位置继续遍历
        if(stackList[len-1]!=NULL)
        {
            l=stackList[len-1];
        }
        //否则从头开始遍历
        else{
            l=ev[stack[len-1][0]];
        }

        while (l!=NULL)
        {
            if(l->index!=rootIndex)
            {   
                //子节点没有计算 
                if(!isUse[l->index])
                {
                    break;
                }
            }
            l=l->next;
        }

        //子节点计算完毕 出栈
        if(l==NULL)
        {
            //根据子节点分数计算操作次数
            long long max=0;
            int num=0;

            l=ev[stack[len-1][0]];
            while (l!=NULL)
            {
                int newIndex=l->index;
                if(newIndex!=rootIndex)
                {   
                   
                    //这样计算只用搜索一次子节点就行了
                    if(input[newIndex]>max)
                    {
                        resultValue+=num*(input[newIndex]-max);
                        max=input[newIndex];
                    }
                    else{
                        resultValue+=max-input[newIndex];
                    }
                    num++;
                }
                l=l->next;
            }
            //当前节点有子节点  分数更新为子节点的最大分数
            if(num>0)
            {
                input[index]=max;
            }
            

            //出栈
            isUse[index]=1;
            stackList[len-1]=NULL;
            delete stack[len-1];
            len--;
        }
        //遍历子结点  子节点入栈
        else{
            
            //存储当前遍历位置
            stackList[len-1]=l;
            len++;
            stack[len-1]=new int[2];
            stack[len-1][0]=l->index;
            stack[len-1][1]=index;

            //入栈时计算节点数值
            input[l->index]=input[index]+l->value;
        }
        
    }
    
    delete stack;
    delete stackList;

    delete input;
    for(i=0;i<n;i++)
    {
        deleteLinkList(ev[i]);
    }
    delete ev;

    printf("%lld\n",resultValue);
}