NOIP2012 疫情控制

二分答案。

如何检验?

考虑把每个军队贪心的往上跳，一直跳到根，如果跳不到根就能跳到哪算到哪。

然后DFS处理一下根节点的哪个子节点没被控制。

注意，如果一个节点被控制，要么是它上面驻扎有军队，要么是它的所有子节点都被控制。

然后考虑一下，如果一个走到了军队的节点，他还能继续走的距离不够他走回他来的时候经过的根节点的子节点，那么直接让这个军队滚回到他来的时候经过的根节点的子节点，如果不这样做，就需要另一个军队来控制这个叶子节点，解不会更优。

然后把剩下的没有滚回去而继续留在根的军队拿出来，按照剩余时间从大到小排序，并且把没有被控制的根的子节点按照距离从大到小排序，然后每次取两者最大的对应上，如果最后所有根的子节点都被安排了，则真正答案小于等于当前二分值，反之真正答案大于当前二分值。

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <assert.h>
#include <queue>
using int_t = long long int;
using pair_t = std::pair<int_t, int_t>;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 50000;
const int_t INF = 0x7ffffffffff;
struct Edge
{
    int_t to;
    int_t dis;
};
std::vector<Edge> graph[LARGE + 1];
int_t size[LARGE + 1], parent[LARGE + 1], top[LARGE + 1] = {0, 1}, heavyChd[LARGE + 1], dis[LARGE + 1];
int_t DFSN[LARGE + 1];
int_t byDFSN[LARGE + 1];
int_t seq[LARGE + 1];
int_t pos[LARGE + 1];
int_t inDis[LARGE + 1];
int_t depth[LARGE + 1];
int_t chdRoot[LARGE + 1];
int_t n, m;
void pushEdge(int_t from, int_t to, int_t dis)
{
    graph[from].push_back(Edge{to, dis});
    graph[to].push_back(Edge{from, dis});
}
void DFS1(int_t vertex, int_t from = -1, int_t depth = 1, int_t chdRoot = -1)
{
    parent[vertex] = from;
    size[vertex] = 1;
    ::depth[vertex] = depth;
    int_t maxSize = 0;
    if (from == 1)
    {
        ::chdRoot[vertex] = chdRoot = vertex;
    }
    ::chdRoot[vertex] = chdRoot;
    for (auto &edge : graph[vertex])
    {
        if (edge.to != from)
        {
            dis[edge.to] = dis[vertex] + edge.dis;
            inDis[edge.to] = edge.dis;
            DFS1(edge.to, vertex, depth + 1, ::chdRoot[vertex]);
            size[vertex] += size[edge.to];
            if (size[edge.to] > maxSize)
            {
                maxSize = size[edge.to];
                heavyChd[vertex] = edge.to;
            }
        }
    }
}
void DFS2(int_t vertex, int_t from = -1)
{
    DFSN[vertex] = ++DFSN[0];
    byDFSN[DFSN[vertex]] = vertex;
    seq[DFSN[vertex]] = inDis[vertex];
    if (heavyChd[vertex] != 0)
    {
        top[heavyChd[vertex]] = top[vertex];
        DFS2(heavyChd[vertex], vertex);
    }
    for (auto &edge : graph[vertex])
    {
        if (edge.to != from && edge.to != heavyChd[vertex])
        {
            top[edge.to] = edge.to;
            DFS2(edge.to, vertex);
        }
    }
}

//一个点从pos开始向上跳，至多走limit距离
pair_t jumpup(int_t vtx, int_t limit)
{
    while (top[vtx] != 1)
    {
        //可以直接跳过一条
        int_t dis = seq[DFSN[vtx]] - seq[DFSN[top[vtx]] - 1];
        if (dis <= limit)
        {
            vtx = parent[top[vtx]];
            limit -= dis;
        }
        //其他情况
        else
            break;
    }
    if (limit == 0)
        return pair_t(vtx, 0);
    //尽力跳到顶
    int_t top = DFSN[::top[vtx]];
    vtx = DFSN[vtx];
    int_t left = top;
    int_t right = vtx;
    int_t max_dis = -INF;
    int_t pos = -1;
    while (left + 1 < right)
    {
        int_t mid = (left + right) / 2;
        if (seq[vtx] - seq[mid] <= limit)
        {
            right = mid - 1;
            if (seq[vtx] - seq[mid] > max_dis)
            {
                max_dis = seq[vtx] - seq[mid];
                pos = mid;
            }
        }
        else
        {
            left = mid + 1;
        }
    }
    for (int_t i = left; i <= right; i++)
    {
        if (limit - (seq[vtx] - seq[i]) >= 0)
        {
            if (seq[vtx] - seq[i] > max_dis)
            {
                max_dis = seq[vtx] - seq[i];
                pos = i;
            }
        }
    }
    return pair_t(byDFSN[pos], limit - max_dis);
}

bool DFS3(int_t vertex, bool *own, int_t from = -1)
{
    if (own[vertex])
        return true;
    bool flag = true;
    int_t count = 0;
    for (auto &edge : graph[vertex])
    {
        if (edge.to != from)
        {
            flag &= DFS3(edge.to, own, vertex);
            count++;
        }
    }
    if (count == 0)
        return own[vertex] = false;
    return own[vertex] = flag;
}

bool check(int_t x)
{
    //某个军队最高能到达的位置
    static int_t pos[LARGE + 1];
    //这个军队到达这里的剩余时间
    static int_t rem[LARGE + 1];
    //某个点现在是否被控制
    static bool own[LARGE + 1];
    //根到某个子节点的距离
    static int_t disroot[LARGE + 1];
    //控制根的一个子节点的军队的ID
    static int_t chd_own[LARGE + 1];
    //到了根又被扔回去的军队ID
    static bool removing[LARGE + 1];
    std::fill(own + 1, own + 1 + n, false);
    std::fill(removing + 1, removing + 1 + n, false);
    std::fill(chd_own + 1, chd_own + 1 + n, -1);
    for (int_t i = 1; i <= m; i++)
    {
        auto ret = jumpup(::pos[i], x);
        pos[i] = ret.first;
        rem[i] = ret.second;
        own[pos[i]] = true;
    }
    own[1] = false;
    //所有到根的军队的id(包括因为最后剩余时间不到边权而被扔回去的)
    std::vector<int_t> toroot;
    //尚未被控制的根节点的子节点的ID(被扔回去的军队占领的节点不包括在内)
    std::vector<int_t> noneown;
    for (int_t i = 1; i <= m; i++)
        if (pos[i] == 1)
        {
            if (chd_own[chdRoot[::pos[i]]] == -1)
            {
                chd_own[chdRoot[::pos[i]]] = i;
            }
            else if (rem[chd_own[chdRoot[::pos[i]]]] > rem[i])
            {
                chd_own[chdRoot[::pos[i]]] = i;
            }
            toroot.push_back(i);
        }

    for (auto &edge : graph[1])
    {
        disroot[edge.to] = edge.dis;
        //这个点没覆盖，并且从这个点来的点走不回去了
        if (DFS3(edge.to, own, 1) == false)
        {
            if (chd_own[edge.to] != -1 && rem[chd_own[edge.to]] <= edge.dis)
            {
                own[edge.to] = true;
                removing[chd_own[edge.to]] = true;
            }
            else
            {
                noneown.push_back(edge.to);
            }
        }
    }

    std::sort(toroot.begin(), toroot.end(), [&](int_t a, int_t b) -> bool { return rem[a] > rem[b]; });
    std::sort(noneown.begin(), noneown.end(), [&](int_t a, int_t b) -> bool { return disroot[a] > disroot[b]; });
    std::deque<int_t> qroot, qchd;
    for (int_t x : toroot)
    {

        if (removing[x] == false)
        {
            qroot.push_back(x);
        }
    }
    for (int_t x : noneown)
    {
        qchd.push_back(x);
    }
    while (qroot.empty() == false && qchd.empty() == false)
    {
        if (rem[qroot.front()] >= disroot[qchd.front()])
        {
            qroot.pop_front();
            qchd.pop_front();
        }
        else
        {
            return false;
        }
    }
    if (qchd.empty() == false && qroot.empty())
        return false;
    return true;
}
int main()
{
    cin >> n;
    for (int_t i = 1; i <= n - 1; i++)
    {
        int_t from, to, weight;
        cin >> from >> to >> weight;
        pushEdge(from, to, weight);
    }

    DFS1(1);
    DFS2(1);
    for (int_t i = 1; i <= n; i++)
    {
        seq[i] += seq[i - 1];
    }
    cin >> m;
    for (int_t i = 1; i <= m; i++)
    {
        cin >> pos[i];
    }
    int_t left = 0;
    int_t right = INF;
    int_t result = INF;
    while (left + 1 < right)
    {
        int_t mid = (left + right) / 2;
        if (check(mid))
        {
            result = std::min(result, mid);
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    for (int_t i = left; i <= right; i++)
    {
        if (check(i))
        {
            result = std::min(i, result);
        }
    }
    cout << result << endl;
    return 0;
}