Luogu P5563 [Celeste-B] No More Running

hl666 / 2024-08-08 / 原文

Celeste，启动！

稍作思考就会发现这题其实很简单，树上路径一眼考虑点分治

对于分治中心，很容易预先求出所有未处理的点到它的距离（模意义下），可以用这些信息来更新中心的答案

考虑剩下的某个未处理的点 $x$，它的答案可能由 $x$ 到分治中心的距离 $dis_x$，拼上分治中心到另一个点 $y$ 的距离 $dis_y$ 构成

由于 $dis_x$ 是已知的定值，且 $dis_x,dis_y\in[0,mod)$，因此不难发现只要根据它们的和要取模/不取模两种情况讨论即可：

若 $dis_x+dis_y$ 不取模，则找到最大的 $dis_y$ 满足 $dis_y\le mod-1-dis_x$，用 $dis_x+dis_y$ 更新答案
若 $dis_x+dis_y$ 取模，则直接找到最大的 $dis_y$，用 $dis_x+dis_y$ 对 $mod$ 取模的值更新答案

用 multiset 维护一下，同时注意 $dis_x$ 与 $dis_y$ 不能来自同一子树这一老生常谈的问题即可

总复杂度 $O(n\log^2 n)$

#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=100005,INF=1e9;
int n,mod,x,y,z,ans[N],dis[N]; vector <pi> v[N]; multiset <int> s;
namespace Point_Divide
{
    int rt,ots,sz[N],mx[N]; bool vis[N];
    inline void getrt(CI now=1,CI fa=0)
    {
        sz[now]=1; mx[now]=0;
        for (auto [to,w]:v[now]) if (to!=fa&&!vis[to])
        getrt(to,now),sz[now]+=sz[to],mx[now]=max(mx[now],sz[to]);
        if (mx[now]=max(mx[now],ots-sz[now]),mx[now]<mx[rt]) rt=now;
    }
    inline void insert(CI now,CI fa=0)
    {
        s.insert(dis[now]); for (auto [to,w]:v[now])
        if (to!=fa&&!vis[to]) dis[to]=(dis[now]+w)&mod,insert(to,now);
    }
    inline void remove(CI now,CI fa=0)
    {
        s.erase(s.find(dis[now])); for (auto [to,w]:v[now])
        if (to!=fa&&!vis[to]) dis[to]=(dis[now]+w)&mod,remove(to,now);
    }
    inline void calc(CI now,CI fa=0)
    {
        auto it=s.upper_bound(mod-dis[now]);
        if (it!=s.begin()) ans[now]=max(ans[now],dis[now]+*(--it));
        if (!s.empty()) ans[now]=max(ans[now],(dis[now]+*s.rbegin())&mod);
        for (auto [to,w]:v[now]) if (to!=fa&&!vis[to]) calc(to,now);
    }
    inline void solve(CI now)
    {
        vis[now]=1; dis[now]=0; insert(now);
        ans[now]=max(ans[now],*s.rbegin());
        for (auto [to,w]:v[now]) if (!vis[to])
        remove(to),calc(to),insert(to); s.clear();
        for (auto [to,w]:v[now]) if (!vis[to])
        mx[rt=0]=INF,ots=sz[to],getrt(to,now),solve(rt);
    }
    inline void divide(CI n)
    {
        mx[rt=0]=INF; ots=n; getrt(); solve(rt);
    }
};
using namespace Point_Divide;
int main()
{
    scanf("%d%d",&n,&mod); --mod;
    for (RI i=1;i<n;++i) scanf("%d%d%d",&x,&y,&z),v[x].push_back(pi(y,z)),v[y].push_back(pi(x,z));
    divide(n); for (RI i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}