默.

考试经过

联考有点慌，真一个不会。。。
找不到多项式做法，四个暴力冲上去，预计爆零
0+15+20+10=45

T1.数据恢复

正解由部分分启发而来，发现菊花图先选1之后没有限制，此时按照\(a/b\)从小到大排序最优
证明可以考虑调整法，其实把贡献式子变一下就好了
那么现在有限制，对于一个当前最优点，如果能选直接选，否则绑在他的父亲后面
就是相当于和父亲缩成了一个点，二者的\(a,b\)直接相加，并查集维护所属关系
如果没有父亲能直接选，就把贡献加上它的\(b\)乘剩下的\(\sum a\)，并把这个删掉
有父亲就和父亲之间算一下贡献，我直接用了set实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
const int N=300050;
int n,fa[N],a[N],b[N];
double v[N];
struct node{
	int id,a,b;
	double v;
	friend bool operator <(node x,node y)
	{
		if(x.v!=y.v)return x.v<y.v;
		return x.id<y.id;
	}
};
set <node> s;
int f[N];bool vis[N];
inline int find(int x)
{
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
signed main()
{
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	cin>>n;int sum=0;
	for(int i=1;i<n;i++)scanf("%lld",&fa[i+1]);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),sum+=a[i];
	for(int i=1;i<=n;i++)
	{
		if(b[i]==0)v[i]=1e9;
		else v[i]=(double)a[i]/(double)b[i];
	}
	for(int i=1;i<=n;i++)s.insert((node){i,a[i],b[i],v[i]});
	int ans=0;vis[0]=1;
	for(int i=1;i<=n;i++)f[i]=i;
	while(s.size())
	{
		node p=*s.begin();s.erase(p);
		int x=p.id,wa=p.a,wb=p.b;
		int fx=find(fa[x]);
		if(vis[fx])
		{	
			ans+=wb*(sum-wa);
			sum-=wa;vis[x]=1;
		}		
		else
		{
			ans+=wa*b[fx];
			s.erase((node){fx,a[fx],b[fx],v[fx]});
			a[fx]+=a[x],b[fx]+=b[x];
			v[fx]=(double)a[fx]/(double)b[fx];
			s.insert((node){fx,a[fx],b[fx],v[fx]});
			f[x]=fx;	
		}
	}
	cout<<ans<<endl;
	return 0;
}

T2.下落的小球

神仙题，大神场切
设子树中大小为\(s\)，叶子的权值之和为\(b\)
对于一个子树，观察到小球下落分成两部分：
先是放空上面的，这个过程落了\(b-s+1\) ,然后把子树里放空，这个落了\(s-1\)
实际上二者互不影响，所以一个可重集排列就是答案
原理？借用Yubai的证明：本质上是一个拆开子树的过程，子树可以拆成更小的子树，而祖先可以每次拆开一个点，所以乘起来就是总共的答案
祖先可以这样理解：把子树一个点拆出来，而所有拆出来的点可以乱排

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e6+10;
struct node{
	int from,to,next;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y)
{
	a[mm].from=x;a[mm].to=y;
	a[mm].next=head[x];head[x]=mm++;
}
int inv[N],jc[N],jcny[N],n,p[N];
inline int C(int x,int y)
{
	if(x<y)return 0;
	if(!y)return 1;
	return jc[x]*jcny[y]%mod*jcny[x-y]%mod;
}
int size[N],sum[N],ans=1;
inline void die(){puts("0");exit(0);}
void dfs(int x)
{
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		dfs(y);
		sum[x]+=sum[y];
		size[x]+=size[y];
	}
	size[x]++;sum[x]+=p[x];
	if(sum[x]-size[x]<0)die();
}
void dfss(int x)
{
	int p1=1,p2=1;
	for(int i=head[x];i;i=a[i].next)
	{	
		int y=a[i].to;
		dfss(y);
		p1=p1*jcny[sum[y]-size[y]]%mod;
		p2=p2*jcny[size[y]]%mod;
	}
	if(head[x])ans=(ans*p1%mod*jc[size[x]-1]%mod*p2%mod*jc[sum[x]-(size[x]-1)]%mod)%mod;
}
signed main()
{
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
	cin>>n;
	inv[0]=jc[0]=jc[1]=jcny[0]=jcny[1]=inv[1]=1;
	for(int i=2;i<=n;i++)
	{
		jc[i]=jc[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		jcny[i]=jcny[i-1]*inv[i]%mod;
	}
	for(int i=1;i<n;i++)
	{
		int x;scanf("%lld",&x);
		add(x,i+1);
	}
	for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
	dfs(1);
	dfss(1);		
	cout<<ans<<endl;
	return 0;
}

T3.消失的运算符

咕

T4.古老的序列问题

咕

考试总结

先打暴力，否则爆零
部分分要仔细分析，还有低错要避免
考试不能犯困啊啊啊