题解 | #和的期望#

数学

对于选择k个，期望可以写作∑(ai+..ak)/(n..n-k+1),对于分子的求和，考虑每个元素的出现次数，在所有的情况中,乘法定理可以说明ai共出现了k(n-1..n-k+1)次，与分母约简后，可以化简为 k/n∑ai,对于除法，使用费马小定理保证，a/bmodp=a*b^mod-2,次方利用快速幂进行计算。

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define maxx 310000
#define mod 998244353
#define int long long
int all[maxx];
int v,e,k,a,b,n,m,t,x,y,l,r,neww,neww1,w,ans,x1,x2;
int sum;
int poww(int i,int j)
{
  if(j==0) return 1;
  if(j==1) return i%mod;
  int q=poww(i,j/2);
  if(j%2==0) return (q*q)%mod;
  else return ((q*q)%mod*i%mod)%mod;
}

signed main()
{
  cin>>n;
  for(int i=1;i<=n;++i)
  {
    cin>>all[i];
    sum=(sum+all[i])%mod;
  }
  for(int i=1;i<=n;++i)
  cout<<((i%mod*sum%mod)%mod*poww(n,mod-2))%mod<<" ";

  
}

动态规划

约定0为A，1是B。

dp[i][j]表示已被(j+1)%2捡走了当前位置的，到树根的最大/小值(0/1),dp1[i][j]表示以i的子孙为根的dp[i][j]的最小/最大值，后者用于前者的转移。

然后依照题目所述进行转移，其中到子孙的每一个位置直接使用dp1[i][(j+1)%2]一步代替,转移顺序可以由深到浅，深度可以dfs计算。

输出dp[1][0]

#include<bits/stdc++.h>
using namespace std;
#define INF 1e20
#define maxx 310000
#define mod 998244353
#define int long long
int dp[maxx][2];
int dp1[maxx][2];
int val[maxx];
int fa[maxx];

int v,e,k,a,b,n,m,t,x,y,l,r,neww,neww1,w,ans,x1,x2;
int sum,mxc;
vector<int> G[maxx];
vector<int> ceng[maxx];
void dfs(int i,int cg)
{
  ceng[cg].push_back(i);
  mxc=max(mxc,cg);
  for(int j=0;j<G[i].size();++j)
  dfs(G[i][j],cg+1);
}
void solve()
{
   

   for(int i=mxc;i>=1;--i)
   for(int j=0;j<ceng[i].size();++j)
    {
       int x=ceng[i][j];
       dp[x][0]=dp1[x][0]=INF;
       dp[x][1]=dp1[x][1]=-INF;
    }  

  for(int i=mxc;i>=1;--i)
    for(int j=0;j<ceng[i].size();++j)
      {int x=ceng[i][j];
      for(int k=0;k<G[x].size();++k)
      {dp[x][0]=min(dp[G[x][k]][0],dp[x][0]);
      dp[x][1]=max(dp[G[x][k]][1],dp[x][1]);
      }
      if(G[x].size()==0)
      {
       dp[x][0]=dp1[x][0]=-val[x];
       dp[x][1]=dp1[x][1]=val[x];
       continue;
      }     
      dp1[x][0]=dp[x][1]-val[x];
      dp1[x][1]=dp[x][0]+val[x];
      dp[x][0]=min(dp1[x][0],dp[x][0]);
      dp[x][1]=max(dp1[x][1],dp[x][1]);
     }
  
}

signed main()
{
  cin>>t;
  for(int i=1;i<=t;++i)
  {
    cin>>n;
    for(int i=2;i<=n;++i) cin>>val[i];
    for(int i=2;i<=n;++i) 
    {cin>>fa[i];
     G[fa[i]].push_back(i);
    }
    dfs(1,1);
    solve();

    cout<<dp1[1][0]<<"\n";
   
   for(int i=1;i<=mxc;++i)
    ceng[i].clear();
    for(int i=1;i<=n;++i)
    G[i].clear();
  

  }
 
  
}

树的直径...