A. 数据恢复
又一次徘徊于正解的边缘.
什么都可以想到，但偏是实现的方法不对.
本来可以直接用 \(set\) 的东西结果非要打线段树.
别的东西推推性质就行了.
A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
#define ll long long
#define ull unsigned ll
#define lf long double
#define lbt(x) (x&(-x))
#define mp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
inline ll read() {
ll res=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return cit?res:-res;
}
} using namespace BSS;
const ll N=3e5+21;
ll m,n,ans,ts;
ll head[N],fa[N],tn[N],to[N],in[N];
multiset<pair<lf,ll> > s;
struct I { ll a,b; lf c; } p[N],bin[N];
ll find(ll x){ return x==fa[x] ? x : fa[x]=find(fa[x]); }
inline void getc(ll x){ p[x].c=1.0*p[x].a/(1.0*p[x].b); }
inline void merge(ll x,ll y){
ans+=p[y].b*p[x].a;
p[y].a+=p[x].a,p[x].a=0;
p[y].b+=p[x].b,p[x].b=0;
getc(y),fa[find(x)]=find(y);
}
signed main(){
File(data);
n=read(); ll u,v,sum=0;
for(int i=2;i<=n;i++) to[i]=read();
for(int i=1;i<=n;i++){
p[i].a=read(),p[i].b=read(),getc(i);
s.insert(mp(p[i].c,i)),in[i]=1,fa[i]=i;
}
while(s.size()){
auto it=s.begin();
u=it->second,v=find(to[u]);
s.erase(s.begin()),in[u]=0;
if(!to[u]) continue;
if(in[v]){
s.erase(s.find(mp(p[v].c,v)));
merge(u,v);
s.insert(mp(p[v].c,v));
}
else{
merge(u,find(v));
}
}
printf("%lld\n",ans);
exit(0);
}
B. 下落的小球
感觉这个题目比 \(T1\) 更可做.
数学题，可以看成两个可重集排列来做.
第一个可重集排列：
考虑每个子树除了要落下自己的子树上的点之外，还要落下祖先上的点.
但是落到每棵子树上的祖先上的点的个数是固定的，只是落到不同子树的顺序不同.
所以这个时候可以给顺序写一个可重集排列.
第二个可重集排列：
每个子树在降落完祖先上的点之后，再去分别降落自己子树上面的点.
发现仍然只需要考虑各个子树的降落顺序.
再写一个可重集排列就行了.
最后两个方案数乘起来就是答案.
B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
#define ll long long
#define ull unsigned ll
#define lf long double
#define lbt(x) (x&(-x))
#define mp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
inline ll read() {
ll res=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return cit?res:-res;
}
} using namespace BSS;
const ll N=1e6+21,mod=1e9+7;
ll m,n,ts,ans;
ll head[N],req[N],frc[N],siz[N],inv[N];
struct I { ll u,v,nxt; } e[N];
inline void add(ll u,ll v){
e[++ts].u=u,e[ts].v=v,e[ts].nxt=head[u];
head[u]=ts;
}
inline ll ksm(ll a,ll b,ll c){
ll res=1; a%=c;
for(;b;b>>=1,a=a*a%c) if(b&1) res=res*a%c;
return res%c;
}
void dfs(ll u){
siz[u]=1; if(!head[u]) return ;
for(int i=head[u];i;i=e[i].nxt){
dfs(e[i].v),siz[u]+=siz[e[i].v];
}
for(int i=head[u];i;i=e[i].nxt){
ans=ans*inv[siz[e[i].v]]%mod*inv[req[e[i].v]-siz[e[i].v]]%mod;
req[u]+=req[e[i].v];
}
// if(req[u]<siz[u]) puts("0"),exit(0);
ans=ans*frc[siz[u]-1]%mod*frc[req[u]-siz[u]+1]%mod;
}
signed main(){
File(ball);
n=read(),frc[0]=1,ans=1; ll u;
for(int i=2;i<=n;i++) u=read(),add(u,i);
for(int i=1;i<=n;i++) req[i]=read(),frc[i]=frc[i-1]*i%mod;
inv[n]=ksm(frc[n],mod-2,mod);
for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
dfs(1),printf("%lld\n",ans),exit(0);
}