题解：P12680 Brooklyn Round 1 & NNOI Round 1 D - Apples

ycy1124 · 2025-08-18 15:44:32 · 题解

前置知识

倍增求 lca。

题意

应该不需要讲了吧。

思路

发现这道题与一般的树上问题不同的地方在于这道题限制了树的深度 s\le 10^3。我们考虑这个限制有什么用。不难发现如果我们能从某一次操作 i 转移到 j 那么需要满足 dep_{w_i} + dep_{w_j} - 2\times dep_{lca(w_i, w_j)} \le t_j - t_i。由于我们任意的的 dep_i \le s\le 10^3，因此我们的 dep_{w_i} + dep_{w_j} - 2 \times dep_{lca(w_i,w_j)}\le 2\times s \le 2\times 10^3。也就是说，如果我们的 t_j - t_i \ge 2\times s 就一定可以转移。因此我们按 t_i 从小到大排序后 dp。枚举到 dp_i 时给所有 t_i - t_j \ge 2\times s 的 dp_j 做一个前缀 \max。然后只需要暴力转移 t_i - t_j < 2\times s 的即可。由于我们的 t_i 互不相同且 2\times s\le 2 \times 10^3，因此我们的复杂度为 \mathcal{O}(m\times s)。可以通过。

代码

#include<bits/stdc++.h>
#define int long long
#define N 80000 + 39
#define M 20000 + 39
#define flush() fwrite(obuf,1,O-obuf,stdout)
#define putchar(x) ((O==obuf+(1<<21))&&(flush(),O=obuf)),*O++=x
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
__inline__ int read(){
    register int x=0;
    register char ch=getchar();
    while(!(ch>='0'&&ch<='9'))
        ch=getchar();
    while(ch>='0'&&ch<='9')
        x=x*10+(ch^48),ch=getchar();
    return x;
}
__inline__ void write(register long long x){
    (x>9)?write(x/10):void();
    putchar((x%10)^48);
}
struct Flush{
    ~Flush(){flush();}
}_;
using namespace std;
struct Node
{
    int w, t, p;
}a[N];
int n, m, s, lca[N][39], dep[N], tmp, ma, ans, dp[M];
vector<int>qwq[N];
inline void dfs(int p, int f)
{
    dep[p] = dep[f] + 1;
    for(int i = 1; i < 39; i ++)
    {
        if(!lca[lca[p][i - 1]][i - 1])
        {
            break;
        }
        lca[p][i] = lca[lca[p][i - 1]][i - 1];
    }
    for(auto it : qwq[p])
    {
        if(it == f)
        {
            continue;
        }
        lca[it][0] = p;
        dfs(it, p);
    }
}
inline bool cmp(Node x1, Node x2)
{
    return x1.t < x2.t;
}
inline int Lca(int u, int v)
{
    if(dep[u] > dep[v])
    {
        swap(u, v);
    }
    int x = dep[v] - dep[u];
    for(int i = 0; i < 39; i ++)
    {
        if((x >> i) & 1)
        {
            v = lca[v][i];
        }
    }
    if(u == v)
    {
        return u;
    }
    for(int i = 39 - 1; i >= 0; i --)
    {
        if(lca[u][i] != lca[v][i])
        {
            u = lca[u][i], v = lca[v][i];
        }
    }
    return lca[u][0];//倍增求lca
}
inline int Max(int x, int y)
{
    return x < y ? y : x;
}
signed main()
{
    n = read(), m = read(), s = read();
    for(int i = 1; i < n; i ++)
    {
        int u = read(), v = read();
        qwq[u].push_back(v);
        qwq[v].push_back(u);
    }
    dep[1] = 1;
    dfs(1, 0);
    for(int i = 1; i <= m; i ++)
    {
        a[i].w = read(), a[i].t = read(), a[i].p = read();
    }
    sort(a + 1, a + m + 1, cmp);
    for(int i = 1; i <= m; i ++)
    {
        while(a[tmp + 1].t + 2 * s <= a[i].t)
        {
            tmp ++;
            ma = Max(ma, dp[tmp]);
        }
        dp[i] = Max(dp[i], ma + a[i].p);//转移前缀max
        if(dep[a[i].w] > a[i].t)//如果从根节点都不能直接到达答案显然为0
        {
            dp[i] = 0;
        }
        for(int j = tmp + 1; j < i; j ++)//暴力转移
        {
            if(dep[a[i].w] + dep[a[j].w] - 2 * dep[Lca(a[i].w, a[j].w)] <= a[i].t - a[j].t)
            {
                dp[i] = Max(dp[i], dp[j] + a[i].p);
            }
        }
        ans = Max(ans, dp[i]);
    }
    write(ans);
    return 0;
}

AC 记录。