自动搬运

查看原文

来自洛谷，原作者为

	EndSaH 我将凋零，凋零在这片我爱的土地。

搬运于2025-08-24 22:12:01，当前版本为作者最后更新于2019-09-20 11:10:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

给定一棵 $n$ 个点的树，边有边权，以及模数 $mod$。对树上每个点都要求出以该点为端点，且权值和模 $mod$ 的余数最大的路径。

Solution

点分治。对当前以 $rt$ 为根的树中所有节点先得出他们到根的距离 $dis _i$（当然是在模意义下的），然后扫一棵子树内的点看如何求答案。发现把两条路径组合起来最多只会超出模数一次，所以对超出模数和不超出模数分别讨论，用 std::multiset 维护即可。（求答案前，先将子树内从 std::multiset 里面全部删除）

不要漏了根的答案，即此时 std::multiset 里的最大值。

$O(n \log ^2 n)$。

Code

竟然只有 116 行...

#include <iostream>
#include <vector>
#include <bitset>
#include <set>

#define fir first
#define sec second

using namespace std;
using pii = pair<int, int>;

const int maxN = 1e5 + 5;

int n, mod, rt, minp, all;
int size[maxN], dis[maxN], ans[maxN];
vector<pii> G[maxN];
bitset<maxN> vis;
multiset<int> S;

inline bool Chkmin(auto& x, const auto& y)
{ return x > y ? x = y, true : false; }

inline bool Chkmax(auto& x, const auto& y)
{ return x < y ? x = y, true : false; }

inline void Mod(int& x)
{ x >= mod ? x -= mod : 0; }

void Getroot(int u, int fa)
{
    int maxp = 0;
    size[u] = 1;
    for (auto& v : G[u]) if (v.fir != fa and !vis[v.fir])
    {
        Getroot(v.fir, u);
        size[u] += size[v.fir];
        Chkmax(maxp, size[v.fir]);
    }
    Chkmax(maxp, all - size[u]);
    if (Chkmin(minp, maxp))
        rt = u;
}

void DFS(int u, int fa)
{
    S.insert(dis[u]);
    for (auto& v : G[u]) if (v.fir != fa and !vis[v.fir])
    {
        Mod(dis[v.fir] = dis[u] + v.sec);
        DFS(v.fir, u);
    }
}

int flag;
// Insert and Erase
void InEr(int u, int fa)
{
    if (flag)
        S.insert(dis[u]);
    else
        S.erase(S.find(dis[u]));
    for (auto& v : G[u]) if (v.fir != fa and !vis[v.fir])
        InEr(v.fir, u);
}

void Getans(int u, int fa)
{
    Chkmax(ans[u], dis[u] + *--S.upper_bound(mod - dis[u] - 1));
    Chkmax(ans[u], (dis[u] + *S.rbegin()) % mod);
    for (auto& v : G[u]) if (v.fir != fa and !vis[v.fir])
        Getans(v.fir, u);
}

void Div(int u)
{
    minp = 1e9, Getroot(u, 0);
    Getroot(rt, 0);
    dis[rt] = 0, DFS(rt, 0);
    for (auto& v : G[rt]) if (!vis[v.fir])
    {
        flag = 0, InEr(v.fir, rt);
        Getans(v.fir, rt);
        flag = 1, InEr(v.fir, rt);
    }
    Chkmax(ans[rt], *S.rbegin());
    flag = 0, InEr(rt, 0);
    vis.set(rt);
    // printf("Now Divide %d:\n", rt);
    // for (int i = 1; i <= n; ++i)
    //     printf("ans[%d] is: %d\n", i, ans[i]);
    // for (int i = 1; i <= n; ++i)
    //     printf("dis[%d] is: %d\n", i, dis[i]);
    for (auto& v : G[rt]) if (!vis[v.fir])
        all = size[v.fir], Div(v.fir);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("wib.in", "r", stdin);
    freopen("wib.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> mod;
    for (int i = n - 1; i; --i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].emplace_back(v, w), G[v].emplace_back(u, w);
    }
    all = n, Div(1);
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << endl;
    return 0;
}