P1079 盈盈一水间官方题解

Gioush OJ · 盈盈一水间 · 2026/09/07 00:00

【部分分：测试点 1∼41\sim 41∼4】

这个时候 $1\leq n\leq 15$ ，显然是很小的，但是如果硬搜索，必然过不了。
可以考虑直接建立完整的图，两个叶子结点间直接建立长度为 $0$ 的边，跑一遍 Hamilton 回路即可。
用经典的状压 DP 可以求解，时间复杂度为 $\mathcal O\left(n^2 2^n\right)$ 。

【部分分：测试点 5∼85\sim 85∼8】

此时所有 $w_i$ 均为 $0$ ，只需要判断可行性。
一条合法路径必然从结点 $1$ 出发，中途不经过结点 $1$ ，最后回到结点 $1$ 。
对非根结点 $u$ ，路径经过 $u$ 时有两种类型：从更浅的结点经过 $u$ 到达叶子，或者从一个叶子经过 $u$ 到达另一个叶子。
因此整棵树会被分成若干条不相交的路径，且每条路径都以叶子结点为端点。
特别地，单个叶子结点也是一条路径。
游览方案合法，等价于每个非叶结点在剥离出的图上度数为 $2$ ，叶子结点的度数为 $1$ 或 $0$ 。
定义 $dp_{u,0/1}$ 表示 $u$ 分别为上述两种类型时， $u$ 的子树能否构成合法的路径。
若 $u$ 是叶子，则 $dp_{u,0}=dp_{u,1}=1$ 。
记 $\operatorname{son}(u)$ 为 $u$ 的儿子结点组成的集合。

\small

dp_{u,0}=\bigvee_{v\in\operatorname{son}(u)} \left(dp_{v,0}\wedge\bigwedge_{\substack{w\in\operatorname{son}(u)\\w\ne v}}dp_{w,1}\right).

dp_{u,1}=\bigvee_{\substack{v,w\in\operatorname{son}(u)\\v\ne w}} \left(dp_{v,0}\wedge dp_{w,0}\wedge \bigwedge_{\substack{t\in\operatorname{son}(u)\\t\ne v,\,t\ne w}}dp_{t,1}\right).

最后判断 $dp_{1,1}$ 是否为真。直接枚举儿子或儿子二元组，最坏时间复杂度为 $\mathcal O(n^2)$ 。

【部分分：测试点 9∼169\sim 169∼16】

这部分没有 $\sum w_i=0$ 的限制，需要在判断可行性的同时最大化经过道路的总权值。
沿用上一档状态，把可行性改成最大价值，并令不合法状态为 $-\infty$ 。
$dp_{u,0}$ 表示子树内留下从 $u$ 向叶子延伸的未完成路径时的最大价值。
$dp_{u,1}$ 表示子树内所有结点均被完整路径合法划分时的最大价值。
对非叶结点，初值为 $-\infty$ 。对叶子结点，有 $dp_{u,0}=dp_{u,1}=0$ 。
设

\operatorname{Sum}(u)=\sum_{v\in\operatorname{son}(u)}dp_{v,1}.

枚举一个儿子 $v$ 继续提供未完成路径，得到

dp_{u,0}=\max_{v\in\operatorname{son}(u)} \left(\operatorname{Sum}(u)-dp_{v,1}+dp_{v,0}+w_{u,v}\right).

枚举两个不同儿子 $v,w$ ，让两条未完成路径在 $u$ 处拼成完整路径，得到

\begin{aligned} dp_{u,1}=\max_{\substack{v,w\in\operatorname{son}(u)\\v\ne w}} \bigl(&\operatorname{Sum}(u)-dp_{v,1}-dp_{w,1}\\ &+dp_{v,0}+dp_{w,0}+w_{u,v}+w_{u,w}\bigr). \end{aligned}

直接枚举儿子二元组，最坏时间复杂度为 $\mathcal O(n^2)$ 。最终答案为 $dp_{1,1}$ 。

【部分分：测试点 17∼1917\sim 1917∼19】

这部分仍满足 $\sum w_i=0$ ，但是 $n$ 的范围变大。
统计满足 $dp_{v,1}=0$ 的儿子数量，记为 $\operatorname{Bad}(u)$ 。这些儿子不能完整留在子树内，必须被当前结点选中。
同时统计满足 $dp_{v,0}=1$ 的儿子，它们可以向当前结点提供一条未完成路径。
计算 $dp_{u,0}$ 时只能选择一个儿子，因此必须有 $\operatorname{Bad}(u)\leq 1$ ，并检查能否选出一个满足 $dp_{v,0}=1$ 的儿子。
计算 $dp_{u,1}$ 时需要选择两个儿子，因此必须有 $\operatorname{Bad}(u)\leq 2$ ，并检查能否选出两个满足 $dp_{v,0}=1$ 的儿子。
每个结点只需要统计上述数量，不再枚举儿子二元组，时间复杂度为 $\mathcal O(n)$ 。

【正解】

根据前面的做法，复杂度瓶颈在于枚举两个儿子。
实际上，每个儿子 $v$ 对答案的影响只和下面这个值有关：

\operatorname{Value}(v)=dp_{v,0}+w_{u,v}-dp_{v,1}.

仍令

\operatorname{Sum}(u)=\sum_{v\in\operatorname{son}(u)}dp_{v,1}.

转移方程可以改写为

\begin{cases} dp_{u,0}=\operatorname{Sum}(u)+\displaystyle\max_{v\in\operatorname{son}(u)}\operatorname{Value}(v),\\[8pt] dp_{u,1}=\operatorname{Sum}(u)+\displaystyle\max_{\substack{v,w\in\operatorname{son}(u)\\v\ne w}} \bigl(\operatorname{Value}(v)+\operatorname{Value}(w)\bigr). \end{cases}

因此只需要维护所有儿子的 $\operatorname{Value}$ 最大值和次大值。
若不存在足够多的合法儿子，对应状态保持为 $-\infty$ 。叶子结点仍有 $dp_{u,0}=dp_{u,1}=0$ 。
最后若 $dp_{1,1}$ 仍为 $-\infty$ ，说明不存在合法方案，输出 Pity!，否则输出 $dp_{1,1}$ 。
每条边只处理一次，总时间复杂度为 $\mathcal O(n)$ ，空间复杂度为 $\mathcal O(n)$ 。

【参考代码】

1#include <cstdio>2#include <cstring>3#include <algorithm>4#define MAXN 2000105using namespace std;6 7int Head[MAXN],Total=0,Fa[MAXN],In1,In2,In3,c,T,n;8long long Dp[MAXN][2];9 10struct edge{11    int St,Ed,Next;12    long long Value;13}Edge[MAXN<<1];14 15void Edge_Add(int St,int Ed,int Value){16    Edge[++Total]={St,Ed,Head[St],Value};17    Head[St]=Total;18}19 20void dfs(int Now){21    bool Leaf=1;22    long long Sum,Max=-1e12,SecM=-1e12;23    Sum=0;24    for(int i=Head[Now];i;i=Edge[i].Next){25        int To=Edge[i].Ed;26        if(To==Fa[Now]) continue;27        Leaf=0;28        Fa[To]=Now;29        dfs(To);30        Sum+=Dp[To][0];31        if(Max<(Dp[To][1]+Edge[i].Value-Dp[To][0])) {SecM=Max;Max=Dp[To][1]+Edge[i].Value-Dp[To][0];}32        else if(Max==(Dp[To][1]+Edge[i].Value-Dp[To][0])) {SecM=Dp[To][1]+Edge[i].Value-Dp[To][0];}33        else {SecM=max(SecM,Dp[To][1]+Edge[i].Value-Dp[To][0]);}34    }35    Dp[Now][1]=Sum+Max;36    Dp[Now][0]=Sum+Max+SecM;37    if(Leaf){Dp[Now][0]=Dp[Now][1]=0;}38    return;39}40 41void Solve(){42    memset(Head,0,sizeof(Head));43    Total=0;44    Fa[1]=1;45    scanf("%d",&n);46    for(int i=1;i<=n;i++) Dp[i][0]=Dp[i][1]=-1000000009;47    for(int i=1;i<=n-1;i++){48        scanf("%d%d%d",&In1,&In2,&In3);49        Edge_Add(In1,In2,In3);50        Edge_Add(In2,In1,In3);51    }52    dfs(1);53    if(Dp[1][0]>=0)printf ("%lld\n",Dp[1][0]);54    else puts("Pity!");55    return;56}57 58int main(){59    freopen("town.in","r",stdin);60    freopen("town.out","w",stdout);61    scanf("%d%d",&c,&T);62    while(T--) Solve();63    return 0;64}