题解：P11850 [TOIP 2023] 关卡地图

· · 题解

题意简述

给定一颗无根树/基环树，有点权，求点权和最大的简单路径的点权和。

分析

  1. m=n-1

树上求最小点权和路径很简单，树形 dp 一下就好了。

void dfs(int u,int fa){
    for(int v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        ans[u]=max(ans[u],dp[u]+dp[v]);
        dp[u]=max(dp[u],dp[v]+a[u]);
    }
}
  1. m=n

本题最复杂的部分。首先，对于基环树，我们需要得到这个环，搜索一下即可。

int vi[N], // 标记
vis[N],viscnt; // 存储正在递归的索引

vector<int>ring; // 存储环上的点编号
int f=0;

void dfs2(int u,int fa){
    if(f)return;
    if(vi[u]){
        int las=viscnt;
        while(vis[viscnt]!=u)
            ring.push_back(vis[viscnt]),viscnt--;
        ring.push_back(u);
        viscnt=las;
        f=1;
        return;
    }
    vi[u]=1;
    vis[++viscnt]=u;
    for (int v:g[u]){
        if(v==fa)continue;
        dfs2(v,u);
    }
    viscnt--;
    vi[u]=0;
}

然后考虑基环树直径的形式。以环上每一个结点为根分别拆分子树，不难得出有两种可能：直径是子树的直径，或者是一个子树以根为端点的极长链——环——另一个子树以根为端点的极长链。

对于第一种情况，分别按 m=n-1 的方法求出子树直径，再取最大值。

对于第二种情况，设环上有 x 个结点。不妨先断环为链，环上第 i 个结点的编号为 r_i\ (1 \le i \le 2x)，环上结点编号 r_i 的子树以根为端点的极长链长度为 dp_{r_i}。我们需要做的就是求环上的这段路径长度。因此作关于环上点权的前缀和，记作 s_i (1 \le i \le 2x)。可推出我们需要求：

\max\{ s_{i-1} - s_j + dp_{r_i} + dp_{r_j} \} \quad(i-1 \ge j,i-j < cnt)

枚举 i，单调队列维护 - s_j + dp_{r_j} 即可。

求 dp 时间复杂度 O(n)，断环为链+前缀和时间复杂度 O(n)，单队时间复杂度 O(n)，总复杂度 O(n)，可通过。

实现

说句闲话：记得断环为链数组开两倍。记得开 long long。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define Mod 1000000007
#define N 200005
#define int ll

int n,m;
int dp[N],ans[N];
vector<int>g[N];
int a[N];
int vi[N],vis[N],viscnt,onring[N],sr[2*N];
vector<int>ring;

void dfs(int u,int fa){
    for(int v:g[u]){
        if(v==fa||onring[v])continue;
        dfs(v,u);
        ans[u]=max(ans[u],dp[u]+dp[v]);
        dp[u]=max(dp[u],dp[v]+a[u]);
    }
}

int f=0;

void dfs2(int u,int fa){
    if(f)return;
    if(vi[u]){
        int las=viscnt;
        while(vis[viscnt]!=u)
            ring.push_back(vis[viscnt]),viscnt--;
        ring.push_back(u);
        viscnt=las;
        f=1;
        return;
    }
    vi[u]=1;
    vis[++viscnt]=u;
    for (int v:g[u]){
        if(v==fa)continue;
        dfs2(v,u);
    }
    viscnt--;
    vi[u]=0;
}

int q[N],tail=0,head=1;

signed main(){
    memset(ans,0xc0,sizeof(ans));
    memset(dp,0xc0,sizeof(ans));

    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int d=-1e9; 
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i]=a[i];
        d=max(d,a[i]);
    }

    if(m==n-1){
        dfs(1,0);
        for(int i=1;i<=n;i++)
            d=max(d,ans[i]);
        cout<<d<<endl;
        return 0; 
    }

    dfs2(1,0);
    int cnt=ring.size();
    ring.insert(ring.begin(),0);
    for(int i=1;i<=cnt;i++)
        onring[ring[i]]=i+1,ring.push_back(ring[i]);
    ring.push_back(0);
    for(int i=1;i<=2*cnt;i++){
        sr[i]=sr[i-1]+a[ring[i]];
    }
    for(int i=1;i<=cnt;i++)
        dfs(ring[i],0);

    for(int i=1;i<=2*cnt;i++){
        while(head<=tail&&q[head]<=i-cnt)head++;
        if(head<=tail&&i-1>=q[head]){
            d=max(d,sr[i-1]-sr[q[head]] + dp[ring[i]]+dp[ring[q[head]]]);
        }
        while(head<=tail&&dp[ring[q[tail]]]-sr[q[tail]] <= dp[ring[i]]-sr[i])tail--;
        q[++tail]=i;
    }

    for(int i=1;i<=n;i++)
        d=max(d,ans[i]);

    cout<<d<<endl;

    return 0;
}