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
        int u,v;cin>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    cout
    ios;
    int T;cinT;
    while(T--)
        solve();
    return 0;
}

    cinn>>k;
    for(int i=1;i
        cin>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
        if(e[i].size()==0) continue;
        for(int j=0;j
            sum[j+1][0]=sum[j][0]+(e[i][j]==i);
            sum[j+1][1]=sum[j][1]+(e[i][j]!=i);
        }
        int tmp=sum[1][0]-sum[1][1];
        for(int j=1;j
            tmp=max(tmp,sum[j-1][0]-sum[j-1][1]);
            ans=max(ans,sum[e[i].size()][0]+sum[j][1]-sum[j][0]+tmp);
        }
    }
    cout
    ios;
    //int T;cinT;
    //while(T--)
        solve();
    return 0;
}

    cinpq;
    int gcd=__gcd(p,q);
    p=p/gcd;
    q=q/gcd;
    int g=sqrt(p+2*q);
    if(g*g!=p+2*q)
    {
        cout
        cout
        cout
        cout
        cout
    //ios;
    int T;cinT;
    while(T--)
        solve();
    return 0;
}

    dp[u]=1;
    int cnt=0;
    for(int v:e[u])
    {
        if(v==fa) continue;
        if(!dfs(v,u)) cnt++;
        dp[u]=dp[u]*dp[v]%mod;
    }
    for(int i=1;i
    cinn;
    for(int i=1;i
        int u,v;cinuv;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    cout
    //ios;
    //int T;cinT;
    //while(T--)
        solve();
    return 0;
}