题解 P1453 【城市环路】

· · 题解

放在前面的话

那个，楼下的dfs找环的确有问题，就在讨论区的那组数据可以把它成功Hack掉

然后几篇题解似乎都是基环树？这么高级的东西我还不会啊

大多人没把dp定义式讲清楚，然我们这种小蒟蒻很尴尬啊，于是我决定献丑一发

然后这题其实是我在图论里找的，结果莫名跑出一道树形dp来，可能Luogu知道我的树形dp太菜了，然后推荐的???

欢迎大家来Hack

题目大意

给你一棵树，点有点权，强制要求一条边只能选一个点，并且还额外命令(S,T)也不能同时选，求满足条件下的最大贡献

Sol

这不是摆明了那你用树形dp切掉的节奏吗？

设f[u][0/1]表示以u为根的字树，u点选或不选的最大贡献

然后转移比较显然，

1.如果u点要选，则它所有的儿子都不能选

2.如果u点不选，那么它的儿子可以选也可以不选

所以转移式就是

f[u][1]=\sum_{u->v}f[v][0] f[u][0]=\sum_{u->v}max(f[v][0],f[v][1])

然后考虑最后的统计答案

以S，T两点分别做一次dp，然后在f[S][0],f[T][0]中取较大值，这样就能保证S,T不可能同时被选了

code

然后就是愉快的上代码环节了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int _=100005;
inline int read()
{
    char ch='!';int z=1,num=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')z=-1,ch=getchar();
    while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return z*num;
}
int n,p[_],fa[_],S,T;
struct ed{int to,next;}e[_<<1];
int cnt,head[_];
double f[_][2];
void link(int u,int v){e[++cnt]=(ed){v,head[u]};head[u]=cnt;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void dfs(int u,int fa)
{
    f[u][1]=p[u];f[u][0]=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;++i)p[i]=read(),fa[i]=i;
    for(int i=1;i<=n;++i)
    {
        int u=read()+1,v=read()+1;
        if(find(u)==find(v)){S=u,T=v;continue;}
        link(u,v);link(v,u);fa[find(v)]=find(u);
    }
    double k,ans=0;
    scanf("%lf",&k);
    dfs(S,0);ans=f[S][0];
    dfs(T,0);ans=max(ans,f[T][0]);
    printf("%.1lf\n",ans*k);
    return 0;
}