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;}