2021 ICPC 南京站+上海站 部分题解

CSDN话题挑战赛第2期

再一次发现一个无比无比菜的自己。。。。

H. Crystalfly

本题难得倒不是思路，是代码的实现。看了下其他大佬的实现，真的惊呼太优雅了。 思路： 1.对于这样的一棵树来说，t的值只能取1到3，可发现2秒实在是没有价值。如果一个点是3s，那说明可去其他1s或3s的点拿完，再去拿这个点的值。 2.如果从x点出发，走向z点，而y点的值是3s，说明可以去完z点转向去y点，这样势必会放弃z点孩子结点的点数。 3.因此采用树形dp来记录各种状态。 //dp[u][0]表示不取以u为根的孩子的最大点数 //dp[u][1]表示取以u为根获得的最大点数 状态的转移： 一般情况：dp[u][1]=max(dp[u][1],dp[u][0]+a[v]);表示走向哪个孩子，获得的点数最大 如果一个孩子结点的t值为3：说明这个结点y的权值是可以拿到的,z是另外一个以u为根结点权值最大or次大的点：dp[u][0]+a[y]+dp[z][0]-(dp[z][1]-a[z]),减去的那一部分是dp[u][0]包含的重复的部分。 此外还需对t为3的情况分两种情况讨论下。

#include 
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int inf=1e18;
const int N=7e5+5;
int n,a[N],t[N],dp[N][2],p[N];
vectore[N];
//dp[u][0]表示不取以u为根的孩子的最大点数
//dp[u][1]表示取以u为根获得的最大点数
void dfs(int u,int fa)
{
    dp[u][1]=dp[u][0]=a[u];
    int mx1=-inf,mx2=-inf;
    for(int v:e[u])
    {
        if(v==fa) continue;
        dfs(v,u);
        dp[u][0]+=dp[v][1]-a[v];
        int tmp=dp[v][0]-dp[v][1]+a[v];
        if(tmp>mx1) mx2=mx1,mx1=tmp;     //最大值
        else if(tmp>mx2) mx2=tmp;       //次大值
    }
    for(int v:e[u])
    {
        if(v==fa) continue;
        dp[u][1]=max(dp[u][1],dp[u][0]+a[v]);
        if(t[v]==3)
        {
            if(dp[v][0]-dp[v][1]+a[v]==mx1)
                dp[u][1]=max(dp[u][1],dp[u][0]+mx2+a[v]);
            else
                dp[u][1]=max(dp[u][1],dp[u][0]+mx1+a[v]);
        }
    }
}
void solve()
{
    cin>>n;
    for(int i=1;ia[i];
    for(int i=1;i>t[i];
    for(int i=1;i>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    coutn>>k;
    for(int i=1;i>a[i];a[i]+=2e6;
        e[a[i]].push_back(a[i]);
        e[a[i]+k].push_back(a[i]);
        g=max(g,a[i]+k);
        mx=max({mx,(int)e[a[i]].size(),(int)e[a[i]+k].size()});
    }
    if(!k)
    {
        cout