题解 P5140 【树枝修剪】

· · 题解

坐标定位，这里是验题人。也不知道什么时候题目被加入公共题库了~~

看着略带感人的通过数，还是把题解搬到这里来吧。

首先吐槽一下出题人的语文水平，叶子节点上的枝条是什么鬼。。。

抛开猥琐的出题人，我们抽象一下这一题的数学模型：就是有一棵树，一些叶子节点有一些东西，另一些叶子节点需要这些东西，你一次只能搬运限定数量的东西，求你从根节点出发完成所有任务到回根节点所走的路径。

记得比赛页面一开始的加粗字吗？

蒟蒻们特别不喜欢数据结构学傻了的dalao（记住这句话）

这句话就是良心的彩色蒟蒻给dalao们的提醒，毕竟这个数据范围很像某个Nlog_{2}N算法。

但是认真思考后就会发现，你进入每个叶子节点的次数是固定的 ，（总会没有人搬完了还进去吧），而且如果有多余的枝条，最好运到它临近的叶子节点。

所以你只要一遍O(N)的dfs就可以了（是不是很带感？）

一开始将需要枝条的叶子节点权值设成负。

回溯的时候如果某个子树能够"自给自足”（子树权值和为0）,就意味着这棵子树不需要往外送枝条也不要往里面运枝条，也就是答案就不要加上这条边的贡献啦。

当然，自给自足的话肯定还要跑这条边过去搬在回来以完成所谓的“自给自足”。
但是，我们还要排除一棵子树上一开始就什么都没有的情况（这一棵树完好无损，过去干嘛？）

出题人后来发现这样的答案贼大，很良心地没有让你取模而是写高精(2333)，(不会压位)所以导致标程跑了0.7s左右，时间复杂度上非常具有迷惑性，于是猥琐的蒟蒻二叉树和彩色蒟蒻一拍即合，没有对标程进一步优化而是减小了数据规模企图造成误导(树剖？倍增？LCA？kruscal重构树？DP？二分？差分？)

（说不定真的有大佬用这些东西做出来了）

标程主要长度就是高精了，下面是蒟蒻二叉树的代码：

#include<bits/stdc++.h>
using namespace std;
int n,f[410000],i,S,T,root,G;
int ant[21000],maxx;
vector <pair<int, int> > q[410000];
bool fronts(int x)
{
    if(ant[x] >= 10)
    {
        ant[x + 1] += ant[x] / 10;
        ant[x] %= 10;
        maxx = max(maxx, x + 1);
        return true;
    }
    return false;
}
void pluse(long long x)
{
    int ws = 0,flag = 0;
    while(x)
    {
        ws ++;
        int c = x % 10;
        ant[ws] += c;
        fronts(ws);
        x /= 10;
    }
    while(fronts(ws + 1)) ws ++,flag = 1;
    if(flag) ws ++;
    maxx = max(maxx, ws);
}
bool findans(int x,int fa)
{
    int flag = 0;
    for(int k = 0;k < q[x].size();k ++)
    {
        int y = q[x][k].first,c = q[x][k].second;
        if(y == fa) continue;
        if(findans(y, x)) flag = 1,
        pluse(1LL * (abs(f[y]) / G + (abs(f[y]) % G != 0) + (f[y] == 0 ? flag : 0)) * c * 2);
        f[x] += f[y];
    }
    if(f[x] != 0 || flag) return true;
    return false; 
}
int main()
{ 
    scanf("%d%d%d", &n, &G, &root);
    for(i = 1;i <= n - 1;i ++)
    {
        int x,y,c;
        scanf("%d%d%d", &x, &y, &c);
        q[x].push_back(make_pair(y, c));
        q[y].push_back(make_pair(x, c));
    }
    scanf("%d%d", &S, &T);
    for(i = 1;i <= S;i ++)
    {
        int x,c;
        scanf("%d%d", &x, &c);
        f[x] += c;
     }
    for(i = 1;i <= T;i ++)
    {
        int x,c;
        scanf("%d%d", &x, &c);
        f[x] -= c;
    }
    findans(root, 0);
    while(fronts(maxx + 1)) maxx ++;
    if(ant[maxx + 1] != 0) maxx ++;
    for(i = maxx;i >= 1;i --) printf("%d",ant[i]);
}