牛客网【每日一题】4月13号 Accumulation Degree

Accumulation Degree

https://ac.nowcoder.com/acm/problem/51180

@[TOC]
本题目传送

题目树学是这个题的简易版，也涉及换根问题，可以先看看这个
树学

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K 64bit
IO Format:%lld

题目描述

Trees are an important component of the natural landscape because of
their prevention of erosion and the provision of a specific
ather-sheltered ecosystem in and under their foliage. Trees have also
been found to play an important role in producing oxygen and reducing
carbon dioxide in the atmosphere, as well as moderating ground
temperatures. They are also significant elements in landscaping and
agriculture, both for their aesthetic appeal and their orchard crops
(such as apples). Wood from trees is a common building material.

Trees also play an intimate role in many of the world's mythologies.
Many scholars are interested in finding peculiar properties about
trees, such as the center of a tree, tree counting, tree coloring.
A(x) is one of such properties.

A(x) (accumulation degree of node x) is defined as follows:

Each edge of the tree has an positive capacity.
The nodes with degree of one in the tree are named terminals.
The flow of each edge can't exceed its capacity.
A(x) is the maximal flow that node x can flow to other terminal nodes.

Since it may be hard to understand the definition, an example is showed below:
在这里插入图片描述

样例分析：

A(1)=11+5+8=24
Details:
1->2 11
1->4->3 5
1->4->5 8(since 1->4 has capacity of 13)

A(2)=5+6=11
Details:
2->1->4->3 5
2->1->4->5 6

A(3)=5
Details: 3->4->5 5

A(4)=11+5+10=26
Details: 4->1->2 11
4->3 5
4->5 10

A(5)=10
Details: 5->4->1->2 10

The accumulation degree of a tree is the maximal accumulation degree among its nodes. Here your task is to find the accumulation degree of the given trees.

输入描述:
The first line of the input is an integer T which indicates the number of test cases. The first line of each test case is a positive integer n. Each of the following n - 1 lines contains three integers x, y, z separated by spaces, representing there is an edge between node x and node y, and the capacity of the edge is z. Nodes are numbered from 1 to n.
All the elements are nonnegative integers no more than 200000. You may assume that the test data are all tree metrics.
输出描述:
For each test case, output the result on a single line.
示例1
输入

输出

题意：

看看样例分析应该就明白了
每个节点都有流量，求出最大流量是多少？

题解：

flow【i】表示i点的流量：
一个点的流量是怎么来的？如果j（j是i的子节点）的流量小于i与j边的容量，flow【i】=flow[j]，如果大于两点之间的容量，flow[i]=i与j的流量
i与j的流量就是i与j的边权，我们用edge[i][j]表示。
可以得到公式：flow[i]=∑min(flow[j],edge[i][j])
因为i有可能有很多子节点，所以加在一起
考虑完i之后，我们来考虑换根
如图：在这里插入图片描述
我们将根从x换成y
题一中（以x为根）
x的流量来自于y，子树2，子树3
y的流量来自于子树1
图二中（以y为根）
x的流量来自子树2，子树3
y的流量来自子树1，x

我们发现换根后，x的流量就没有了y的部分，其他都还在，此时x的流量就是原本的减去从y流向x的部分，new[x]=flow[ x ] - min ( flow[ y ] , edge[ x ] [ y ] ),这个new表示x新的流量

我们再看y，y的流量多了从x流来的部分，y的流量就是flow[y]+min(new[x],edge[x][y])，，因为换根x的流量发生改变（上一段所讲），那流向y的是现在x的流量，而不是换跟前的flow[x].

换根前后，图二中绿***域没有发生改变，也就是父节点改变影响不到子节点

还要注意叶子节点，如果x从根变成叶子节点（x的儿子只有y，当y成为根节点之后，x没有了儿子），x的流量不是上面的公式，而是变成了edge[x][y]，因为没有子节点的流量流向x，只有x与y的边权值，也就是上面讲的式子使用条件是min（x，y），x和y不能为0。

先求出x为根的流量，然后依次换根求出最大值

代码：

#include <bits/stdc++.h>

#define inf 0x7f
typedef long long LL;
using namespace std;
const int maxn = 2e5 + 3;

int n;

int head[maxn], cnt = 0, d[maxn], deg[maxn], f[maxn];
struct edge{
    int x, y;
    int next;
    int w;
}edge[maxn * 2];

void init()
{  
      cnt = 0;
    memset(head, -1, sizeof(head));

    memset(d, 0, sizeof(d));
    memset(deg, 0, sizeof(deg));
}

void addedge(int x, int y, int w)
{
    edge[cnt].x = x;
    edge[cnt].y = y;
    edge[cnt].w = w;
    edge[cnt].next = head[x];
    head[x] = cnt++;

}

void dfs(int root, int fa) 
{
    int ans = 0;
    for(int i = head[root]; i != -1; i = edge[i].next){
        int y = edge[i].y;
        if(y == fa){
            continue;
        }
        if(deg[y] == 1){//如果y只有一个子节点，y的流量只能是root与y的边权值 
            ans += edge[i].w;
        }
        else{
            dfs(y, root);
            ans += min(d[y], edge[i].w);
        }
    }
    d[root] = ans 
    return ;
}//先求出节点x的流量 

void dp(int x, int fa)
{
    for(int i = head[x]; i != -1; i = edge[i].next){
        int y = edge[i].y;
        if(edge[i].y == fa)continue;
        if(deg[x] == 1){
            f[y] = d[y] + edge[i].w;
        }
        else{
            f[y] = d[y] + min(f[x] - min(d[y], edge[i].w), edge[i].w);//核心公式 
        }
        dp(y, x);
    }
}//从x不断换根 

int main()
{
    int t;
   cin>>t;
       int x, y, w;
    while(t--){
        init();//初始化 
        scanf("%d", &n);
        for(int i = 0; i < n - 1; i++){

            scanf("%d%d%d", &x, &y, &w);
            addedge(x, y, w);//添边 
            addedge(y, x, w);//添边 
                deg[x]++;//deg用于判断这个点有几个子节点 
                 deg[y]++;
        }

        int s = 1;
        dfs(s, 0);//求x的流量 
        f[s] = d[s];
        dp(s, 0);//不断换根 
        int ans = 0;
        for(int i = 1; i <= n; i++){
            ans = max(ans, f[i]);
        }
        printf("%d\n", ans);

    }
    return 0;
}