题解：P6615 草莓 Strawberry

· · 题解

题解：P6615 草莓 Strawberry

题目传送门

这篇题解的篇幅较长，如有不懂的地方，欢迎私信向作者提问，作者在正常情况下会在 1~3 天内回复。

题意

题目要你找一个树意义下的连通分量 S，使得 \min_{u,v\in S}\text{dist}(u,v)\times \sum_{u\in S}{a_u} 最大化，输出这个最大值。

思路

这道题很适合沿着部分分开始做。 :::info[Subtask 5] 直接输出 0 即可。 ::: :::info[Subtask 1~3] 各种形式的暴力。 ::: :::info[Subtask 4] 令 D_{\max}{u} 表示 \sum_{\max}{\text{dist}(u,v)}， 即以点 u 为其中一个端点的最长路径。

首先以一个点 u 为其中一个端点的最长路径的另一个端点一定是 1 或 n。换句话说，D_{\max}{u}=\max(\text{dist}(1,u),\text{dist}(u,n))。

如果我们设定最小跳跃距离为 W，那么只有满足 D_{max}(u) \ge W 的点 u 才能被纳入集合 S。

只要 W \le \text{dist}(1, n)（链长），端点 1 和 n 就能相互跳跃。

那么，所有满足 D_{max}(u) \ge W 的点 u 都可以通过 u \to 1 或 u \to n 的方式连通。

那么就存在一个贪心解法：计算所有点的 val_u = \max(\text{dist}(u, 1), \text{dist}(u, n))。将点按 val_u 从大到小排序。枚举 W = val_u，此时前缀中的所有点都可以加入集合，计算 \text{sum}(a) \times W 更新答案。 ::: :::info[Subtask 6] 考虑把 Subtask 4 的解法推广至一个树。

首先，树上距离任意节点 u 最远的节点，一定是直径的端点之一（直径的两个端点分别记为 L 和 R）。

所以，我们可以在这条直径上完成 Subtask 4 的操作，定义 val_u = \max(\text{dist}(u, L), \text{dist}(u, R))。这样，对于每个 u，只需要考虑这一条直径。

仅仅知道 u 到 L 或 R 远还不够，我们需要这些路径在集合 G 中共存时，满足“所有路径长度 \ge W”。

考虑链的情况：如果 W \le \text{dist}(1, n)（链长），那么端点 1 和 n 是连通的（或者说它们之间有路径且长度足够）。任何满足 \text{dist}(u, 1) \ge W 的点 u，可以通过 u \to 1 加入；而任何满足 \text{dist}(v, n) \ge W 的点 v，可以通过 v \to n 加入。

因为 1 和 n 在“枢纽”集合里，所以 u \to 1 和 v \to n 这些路径虽然方向不同，但在逻辑上是合法的（基于 1, n 互通）。

树的情况：假设我们选取了一个阈值 W。

情况 A：W > \text{直径}。此时 L 和 R 之间的距离都不够 W。不可能存在两个不同的分支还能互相连接。此时只能是以某一个点为中心的一条“单链”或者“菊花图”的一个分支。也就是只能选 L 这一侧或者 R 这一侧。

情况 B：W \le \text{直径}。此时 L 到 R 的路径长度 \ge W。这意味着 L 和 R 都可以作为“枢纽”。

对于任意点 u，如果 \text{dist}(u, L) \ge W，我们将路径 u \to L 加入 G。

对于任意点 v，如果 \text{dist}(v, R) \ge W，我们将路径 v \to R 加入 G。

由于 \text{dist}(L, R) \ge W，虽然 u 连向 L，v 连向 R，但因为 L,R 也是相互“达标”的，所以整个结构是合法的。

时间复杂度 O(n\log n)，瓶颈在排序。 :::

正解具体实现 & 代码

:::info[实现]

  1. 找到直径端点 L，R。
  2. 计算所有点到 L 和 R 的距离 dL_i,dR_i。
  3. 计算 val_i = \max(dL_i, dR_i)。
  4. 将所有点按 val_i 降序排序。
  5. 枚举排序后的前 k 个点作为集合 S。这里要处理 L 和 R 是否连通的边界情况（即瓶颈长度是否大于直径）。 ::: :::success[代码] 代码丑。 
    #include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;a++)
#define pb push_back
#define int long long
using namespace std;
const int N=220005;
int n,a[N],dL[N],dR[N],p[N],ans,sum;
struct Edge{
int v,w;
};
vector<Edge> g[N];
int bfs(int s,int* d){
For(i,1,n)d[i]=-1;
d[s]=0;
queue<int> q;
q.push(s);
int f=s;
while(q.size()){
    int u=q.front();
    q.pop();
    if(d[u]>d[f])f=u;
    for(auto [v,w]:g[u])if(d[v]==-1){
        d[v]=d[u]+w;
        q.push(v);
    }
}
return f;
}
//处理单侧贪心的情况的函数 
void solve(int* d){
sum=0;
For(i,1,n){
    sum+=a[p[i]];
    ans=max(ans,sum*d[p[i]]);
}
}
signed main(){
cin>>n;
For(i,1,n)
    cin>>a[i];
For(i,2,n){
    int u,v,w;
    cin>>u>>v>>w;
    g[u].pb({v,w});
    g[v].pb({u,w});
}
//三次 BFS 确定直径及其端点 L,R
int L=bfs(1,dL),R=bfs(L,dL);
bfs(R,dR);
iota(p+1,p+1+n,1); //相当于 For(i,1,n) p[i]=i; 
//连通块仅挂在直径的一端 (L 或 R)
//此时不通过直径跨越，退化为以 L 或 R 为根的单链贪心
sort(p+1,p+1+n,[&](int x,int y){return dL[x]>dL[y];});
solve(dL);
sort(p+1,p+1+n,[&](int x,int y){return dR[x]>dR[y];});
solve(dR);
//连通块利用直径作为桥梁 (跨越 L-R)
sort(p+1,p+1+n,[&](int x,int y){return max(dL[x],dR[x])>max(dL[y],dR[y]);});
sum=0;
int diam=dL[R];
For(i,1,n){
    sum+=a[p[i]];
    //若距离 W > 直径，则无法跨越，退化为单侧(已被策略A覆盖)
    //此有效距离取 min(点到端点最大距离, 直径长度)
    ans=max(ans,sum*min(max(dL[p[i]],dR[p[i]]),diam));
}
cout<<ans;
return 0;
}

    :::