题解：P14706 [ICPC 2023 Tehran R] Cup of Tea

点亮花火 · 2026-11-09 21:41:14 · 题解

来一个 O(n\log^2 n) 的做法。

首先你可以考虑一个暴力建图的做法，你发现一定是从某个茶馆开始走，每次走不超过 k 的距离，于是你尝试把每个茶馆向周围不超过 k 的点连边，然后从 1 开始进行最短路，但暴力建图是平方的。

考虑如何优化建这些边，树上距离不超过 k 的点，你发现可以点分治。对于当前分治中心，求出每个点到分治中心距离 d_i，则对于一个茶馆 u 能到的 v 是一段应当是 d 上的一段前缀，于是对于点分治每层，可以考虑按照距离 d 前缀优化建图，总边数是 O(n\log n) 级别的，最后跑一遍 dij，时间复杂度 O(n \log^2 n)。

::::success[code]

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int,int>
#define fi first
#define se second

const int maxn = 3e5 + 10;
const int maxv = maxn * 21;
const int inf = (1ll << 61);

int n,k,rt,tot,cnt;
int a[maxn],siz[maxn],mx[maxn];
bool vis[maxn];

vector<pii> G[maxn];

struct edge{
    int v,w;
};
vector<edge> H[maxv];

int dis[maxv];

pii b[maxn];
int id[maxn],num;

void add(int u,int v,int w) {H[u].push_back({v,w});}

void getroot(int u,int fa)
{
    siz[u] = 1;
    mx[u] = 0;

    for(auto it : G[u])
    {
        int v = it.fi;
        if(v == fa || vis[v]) continue;

        getroot(v,u);
        siz[u] += siz[v];
        mx[u] = max(mx[u],siz[v]);
    }

    mx[u] = max(mx[u],tot - siz[u]);
    if(mx[u] < mx[rt]) rt = u;
}

void getdis(int u,int fa,int d)
{
    if(d > k) return;
    b[++num] = {d,u};
    for(auto it : G[u])
    {
        int v = it.fi,w = it.se;
        if(v == fa || vis[v]) continue;
        getdis(v,u,d + w);
    }
}

void build(int u)
{
    num = 0;
    getdis(u,0,0);
    sort(b + 1,b + num + 1);
    for(int i = 1;i <= num;i++)
    {
        id[i] = ++cnt;
        add(id[i],b[i].se,b[i].fi);
        if(i > 1) add(id[i],id[i - 1],0);
    }

    int j = num;

    for(int i = 1;i <= num;i++)
    {
        while(j && b[i].fi + b[j].fi > k) j--;
        int x = b[i].se;
        if(a[x] && j) add(x,id[j],b[i].fi);
    }
}

void divide(int u)
{
    vis[u] = 1;
    build(u);
    for(auto it : G[u])
    {
        int v = it.fi;
        if(vis[v]) continue;

        tot = siz[v];
        mx[rt = 0] = inf;
        getroot(v,u);
        getroot(rt,0);
        divide(rt);
    }
}

void dij(int s)
{
    for(int i = 1;i <= cnt;i++) dis[i] = inf;
    priority_queue<pii,vector<pii>,greater<pii>> q;
    dis[s] = 0; q.push({0,s});

    while(!q.empty())
    {
        auto it = q.top();
        q.pop();

        int u = it.se,d = it.fi;
        if(d != dis[u]) continue;
        for(auto e : H[u])
        {
            int v = e.v,w = e.w;
            if(dis[v] > d + w)
            {
                dis[v] = d + w;
                q.push({dis[v],v});
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin >> n >> k;
    for(int i = 1;i < n;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;

        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }

    for(int i = 1;i <= n;i++) cin >> a[i];

    cnt = n;
    tot = n;
    mx[rt = 0] = inf;
    getroot(1,0);
    getroot(rt,0);
    divide(rt);

    dij(1);

    for(int i = 2;i <= n;i++) cout << (dis[i] == inf ? -1 : dis[i]) << ' ';
    cout << '\n';
    return 0;
}

::::