自动搬运

查看原文

来自洛谷，原作者为

	ycy1124 ENTJ-A | 有事私。| 清关了，私信基本也不会回关（除非满足条件），但可以支持小号回关 | 出去玩去了。不在线。微信可能上。

搬运于2025-08-24 23:17:22，当前版本为作者最后更新于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 记录。