https://zybuluo.com/ysner/note/1120723

题面

原题

某省选强化题

大致意思是给你一颗树，选父亲后才能选儿子。

每个点对答案的贡献为你在第几次选这个点 × 该点权值

问取完所有点最小答案是多少。

• 对于\(60pts\) \(n\leq1000\)
• 对于\(100pts\) \(n\leq500000\)

解析

贪心没学好，_ _ _ _ _(自己yy）

答案要求的其实是个选取序列。。。

我们可以发现，要保证答案最优性，最大点取的时间越小越好。

又可以发现，只要最大点父亲已选，下一个点选最大点肯定最优。

这时我们确定了一部分顺序，可以想，为什么不能把已确定的、前后相邻选的两点合并起来呢？

现在问题就是如何在几个大点中作抉择了。

可以发现，此时如果大点\(a[i]/t[i]\)越大(\(a[i]\)是权值和，\(t[i]\)是时间和)，就是性价比越高，先选越优。

对于\(n\leq1000\)

显然\(a[i]/t[i]\)看起来有点鬼

我们要用更有区分度的比较方式

如果\(a[i]/t[i]>a[j]/t[j]\)

那么\(a[i]*t[j]>a[j]*t[i]\)

于是每次按着贪心策略合并点，对答案的贡献为其父亲选完所用时间×点权值，再把新点与被合并点的儿子相连即可。

int main()

{

  while(233)

    {

      memset(h,-1,sizeof(h));ans=0;cnt=0;

      n=gi();r=gi();

      if(!n&&!r) break;t[0]=1;

      fp(i,1,n) a[i]=gi(),t[i]=1;

      fp(i,1,n-1)

	{

	  re int u=gi(),v=gi();

	  add(u,v);f[v]=u;

	}

      f[r]=0;

      re int res=n;

      while(res--)

	{

	  re int mx=1;

	  fp(i,2,n)

	    if(a[i]*t[mx]>a[mx]*t[i]) mx=i;

	  ans+=a[mx]*t[f[mx]];

	  a[f[mx]]+=a[mx];t[f[mx]]+=t[mx];

	  for(re int i=h[mx];i+1;i=e[i].nxt)

	    {

	      re int v=e[i].to;

	      f[v]=f[mx];

	      add(f[mx],v);

	    }

	  a[mx]=-1;

	}

      printf("%lld\n",ans);

    }

  return 0;

}

Update:发现一个很蛋疼的问题：用并查集就不用新建边了。

对于\(n\leq500000\)

裸贪心是\(O(n^2)\)的。

我们需要一个能马上提供最大点的堆来降低复杂度。

struct node{int u,sz;ll w;bool operator < (const node &o) const {return w*o.sz>o.w*sz;}};

priority_queue<node> Q;

il void dfs(re int u)

{

  vis[u]=1;++tim;

  for(re int i=h[u];i+1;i=e[i].nxt)

    {

      re int v=e[i].to;

      if(vis[v]) {puts("-1");exit(0);}

      dfs(v);

    }

}

il int find(re int x){return x==F[x]?x:F[x]=find(F[x]);}

int main()

{

    memset(h,-1,sizeof(h));ans=0;

    n=gi();

    fp(i,1,n) f[i]=gi(),add(f[i],i);

    dfs(0);if(tim<=n) return puts("-1"),0;

    fp(i,0,n) F[i]=i,sz[i]=1;

    fp(i,1,n) w[i]=gi(),Q.push((node){i,1,w[i]});

    re int u,p;

    while(!Q.empty())

      {

	node s=Q.top();Q.pop();u=find(s.u);

	if(sz[u]^s.sz) continue;//扔掉不符合当前情况的决策

	F[u]=p=find(f[u]);

	ans+=w[u]*sz[p];

	w[p]+=w[u];sz[p]+=sz[u];

	if(p) Q.push((node){p,sz[p],w[p]});

      }

    printf("%lld\n",ans);

  return 0;

}