资讯详情

树上路径 1（dmy）

题目描述

给你一个 \(n\) 个点的以 \(1\) 为根的树。

给你 \(m\) 条树上的简单路径，每个路径有个权值 \(a_i\)。

要求选择一些路径，使得每个点至多在一条路径上，并且路径的权值和最大。

其中 \(1\le n,m \le 2\times 10^3\)。

思路

首先你要知道什么是简单路径，简单路径是各顶点不重复的路径，因此是独一无二的。

---

在一棵树上，对于一个路径 \((u,v,w)\)，我们下意识想到分成 \(u\to \text{LCA}\) 和 \(\text{LCA} \to v\)。

所以我们就预处理出来每一个路径 \(u,v\) 的 \(\text{LCA}\)，先不管有没有用，先预处理出来再说。

因为 \(n\le 2\times 10^3\)，我们可以直接暴力预处理。

这样预处理出来还是很有用的，对于一条路径，我们只需要在 \(\text{LCA}\) 处决策即可。

---

考虑树形 \(\text{dp}\)，我们可以这样定义状态：

我们让 \(s\) 作为保底，也就是 \(s[u]\) 代表 \(u\) 完全闲置，不选择任何跨越 \(u\) 的路径，但是其子节点处于自由状态，则：

\[s[u]=\sum\limits_{u\in son_u} dp[v] \]

\(dp[u]\) 代表，以 \(u\) 为根的子树，完全不受祖先干扰时的最大路径，显然这样是能覆盖所有情况的，哪怕不考虑祖先覆盖，到了祖先那一层也会考虑到节点 \(u\)，答案是 \(dp[1]\)。

自由状态包含强制闲置状态，因此不劣于强制闲置状态，所以 \(dp[u]\ge s[u]\)，我们定义损失：

\[l[x]=dp[x]-s[x] \]

表示，如果 \(x\) 被祖先强制覆盖，子树 \(x\) 的收益会减少多少。

---

对于一条路径 \((u,v,w)\)，假设其 \(\text{LCA}\) 为 \(k\)，我们只需要在 \(k\) 处选择是否选取。

我们如果选择，那么路径会覆盖 \(u\to k\) 和 \(v\to k\) 的所有节点，也就是让他们强制覆盖。

因此，选这个路径的总收益为：

\[s[k]+w-\sum\limits_{x\in (u\to k)}l[x]-\sum\limits_{x\in (v\to k)}l[x] \]

相对于 \(s[k]\) 的增量：

\[\Delta = w-\sum\limits_{x\in (u\to k)}l[x]-\sum\limits_{x\in (v\to k)}l[x] \]

因为节点 \(k\) 只能选择一条 \(\text{LCA}\) 为 \(k\) 的路径，因此：

\[dp[k]=s[k]+\max(0,\max\limits_{w,lca(u,v)=k}\Delta_{(u,v,w)}) \]

好的，做出来了

---

时间复杂度

• 预处理 \(\text{LCA}\) ：\(\mathcal{O}(nm)\)。

• \(\text{dp}\) 转移的时候，需要遍历每条路径，最坏 \(\mathcal{O}(nm)\)。

• 总时间复杂度 \(\mathcal{O}(nm)\)。

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=2003;int n,m;
int pre[N],dep[N];
int dp[N],s[N];
vector<int> g[N];
struct road {int s,t,len;
};
vector<road> r[N];
void dfs(int u) {for(auto v:g[u]) {dfs(v);s[u]+=dp[v];}dp[u]=s[u];int t=0;for(auto [a,b,c]:r[u]) {int tmp=0;int x=a;while(x!=u) {tmp+=(s[x]-dp[x]);x=pre[x];}x=b;while(x!=u) {tmp+=s[x]-dp[x];x=pre[x];}tmp+=c;t=max(t,tmp);}dp[u]+=t;
}
void init() {}
void solve() {init();cin>>n>>m;for(int i=2; i<=n; i++) {cin>>pre[i];g[pre[i]].push_back(i);dep[i]=dep[pre[i]]+1;}for(int i=1,u,v,w; i<=m; i++) {cin>>u>>v>>w;int x=u,y=v;while(x!=y) {if(dep[x]>dep[y])x=pre[x];else y=pre[y];}r[x].push_back({u,v,w});}dfs(1);cout<<dp[1];
}signed main() {int T=1;while(T--) {solve();}
}

通过倍增可以优化至 \(\mathcal{O}((n+m)\log n)\)。