lyzlyz?lyzlyz!

惯例开坑。

任务栏：

订正了几题？3/3

BZOJ刷题量？306/300

撒花~~~~~~

T1

一棵有根树，选择点u会获得w[u]的收益（w[u]可能为负），若选择了u且u的k[u]个祖先有一个没有被选，需要额外付出p[u]的代价，最大化收益。

题目名称flow已经暴露了一切。。。。（然而我并不会）

首先考虑网络流，若w[u]>0，源连u，流量w[u]，ans加上w[u]，否则u连汇，流量-w[u]。对于k[u]的限制，将u的k[u]个祖先向n+u连流量为inf的边，n+u连u，流量为p[u]，表示要么全选祖先，要么付出代价，跑最小割即可。

发现这样的边数是n²的，主要是树上一段连续的向某个点连inf的边，可以树链剖分然后用类似线段树的形态加边。

T2

有n个按键，按错按键i的概率为p[i]。一段长度为x的连续成功按键得分为：

[tex]f(x)=tan(\frac{x}{n})e^{arcsin(\frac{0.8x}{n})}[/tex]

求得分的期望。

OSU的即视感，然而这个得分函数是什么玩意？

SB出题人表示：可以用一个十五次多项式来逼近f(x)。

然后就可以用dp来推辣！

然而精度误差着实有些惊人。。。

T3

有一棵树，有白点和黑点，每次随机选择一个起点，然后以随机顺序遍历其所有儿子，若所有黑点都遍历完则结束，否则回到父亲，问走过路径的期望长度。

令S[u]为遍历完u的子树的步数，E[u]为在u的子树中结束遍历的步数。

不妨假定：若u的子树中有黑点，则u为黑点。

若枚举顺序确定，显然发现：最后一个黑儿子之前的所有儿子都必须遍历完。

再推广到不确定的情况，若有m个黑儿子，每个黑儿子成为最后一个黑儿子的概率为1/m，每个白儿子出现在最后一个黑儿子之后的概率为1/(m+1)。

那么：

[tex]e[u]=\frac{m}{m+1}\sum_{v\in{whitenode}}s[v]+\frac{m-1}{m}\sum_{v\in{blacknode}}s[v]+exp[/tex]

[tex]exp=\frac{1}{m}\sum_{v\in{blacknode}}e[v][/tex]

对于根不确定的dp，可以任意确定一个根做一次dp，然后再做一次dfs，利用父亲的信息来更新儿子来求得儿子为根的情况。

[Codes]

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
const int inf=1000000007;
int n,i,j,ans,edgenum,Edgenum,cnt,time;
int Head[M],Vet[M],Next[M],tid[M],pre[M],son[M],Size[M],top[M];
int fa[M],w[M],a[M],b[M],head[M],vet[M*25],next[M*25],size[M*25],dis[M],h[M];
void Addedge(int x,int y){
	Vet[++Edgenum]=y;
	Next[Edgenum]=Head[x];
	Head[x]=Edgenum;
}
void addedge(int x,int y,int z){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
	size[edgenum]=z;
	vet[++edgenum]=x;
	next[edgenum]=head[y];
	head[y]=edgenum;
	size[edgenum]=0;
}
void build(int l,int r,int p){
	cnt=max(cnt,p+2*n+1);
	if (p!=1)addedge(p+2*n+1,(p>>1)+2*n+1,inf);
	if (l==r){addedge(l,p+2*n+1,inf);return;}
	int mid=l+r>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1^1);
}
void update(int x,int y,int l,int r,int p){
	if (x==l&&y==r){
		addedge(p+2*n+1,n+i,inf);
		return;
	}
	int mid=l+r>>1;
	if (y<=mid)update(x,y,l,mid,p<<1);
		else if (x>mid)update(x,y,mid+1,r,p<<1^1);
			else update(x,mid,l,mid,p<<1),update(mid+1,y,mid+1,r,p<<1^1);
}
int bfs(){
	int l=1,r=1;
	for (int i=1;i<=cnt;i++)dis[i]=-1;
	while (l<=r){
		int u=h[l];
		for (int e=head[u];e;e=next[e]){
			int v=vet[e];
			if (size[e]&&dis[v]<0){
				dis[v]=dis[u]+1;
				h[++r]=v;
			}
		}
		l++;
	}
	if (dis[2*n+1]<0)return 0;else return 1;
}
int dfs(int u,int aug){
	if (u==2*n+1)return aug;
	int flow=0;
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (size[e]&&dis[v]==dis[u]+1){
			int tmp=dfs(v,min(aug-flow,size[e]));
			size[e]-=tmp;
			size[e^1]+=tmp;
			flow+=tmp;
			if (flow==aug)return flow;
		}
	}
	if (!flow)dis[u]=-1;
	return flow;
}
void dfs1(int u){
	Size[u]=1;son[u]=0;
	for (int e=Head[u];e;e=Next[e]){
		int v=Vet[e];
		dfs1(v);
		Size[u]+=Size[v];
		if (!son[u]||Size[v]>Size[son[u]])son[u]=v;
	}
}
void dfs2(int u,int ance){
	tid[u]=++time;pre[time]=u;top[u]=ance;
	if (son[u])dfs2(son[u],ance);
	for (int e=Head[u];e;e=Next[e]){
		int v=Vet[e];
		if (v==son[u])continue;
		dfs2(v,v);
	}
}
int main(){
	edgenum=1;
	scanf("%d",&n);
	for (i=1;i<=n;i++){
		scanf("%d%d%d%d",&fa[i],&w[i],&a[i],&b[i]);
		Addedge(fa[i],i);
	}
	dfs1(1);
	dfs2(1,1);
	for (i=1;i<=n;i++){
		if (w[i]>0)addedge(tid[i],2*n+1,w[i]),ans+=w[i];
			else addedge(0,tid[i],-w[i]);
	}
	build(1,time,1);
	for (i=1;i<=n;i++){
		int x=fa[pre[i]],r=0;
		while (a[pre[i]]){
			if (tid[x]-tid[top[x]]+1>=a[pre[i]])update(tid[x]-a[pre[i]]+1,tid[x],1,n,1),a[pre[i]]=0;
				else update(tid[top[x]],tid[x],1,n,1),a[pre[i]]-=tid[x]-tid[top[x]]+1;
			x=fa[top[x]];
		}
		addedge(n+i,i,b[pre[i]]);
	}
	while (bfs())ans-=dfs(0,inf);
	printf("%d\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const double xishu[16]={-4.24979841297e-12,1.00000008983,0.799978648796,0.654614705503,0.403827353614,0.802129354545,-3.93434353775,23.8762214791,-92.5788259887,253.804090672,-491.286508915,670.149961274,-630.033886213,389.181543743,-142.378854835,23.4766536318};
int n,i,j,k;
double a[100010],c[20][20],dp[100010][20],ans;
int main(){
	scanf("%d",&n);
	c[0][0]=1;
	for (i=1;i<=15;i++){
		c[i][0]=c[i-1][0]/n;
		for (j=1;j<i;j++)c[i][j]=c[i-1][j-1]+c[i-1][j]/n;
		c[i][i]=1;
	}
	for (i=1;i<=n;i++)scanf("%lf",&a[i]);
	a[n+1]=1;
	dp[0][0]=1;
	for (i=1;i<=n;i++){
		for (j=0;j<=15;j++){
			for (k=0;k<=j;k++)dp[i][j]+=dp[i-1][k]*c[j][k];
			dp[i][j]*=1-a[i];
			if (!j)dp[i][j]+=a[i];
			ans+=dp[i][j]*a[i+1]*xishu[j];
		}
	}
	ans=ans*n;
	printf("%.6lf\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
int n,m,i,x,y,edgenum,N;
int head[M],vet[M],next[M],Cnt[M],size[M],col[M],B[M],W[M];
long double E[M],V[M],ans;
void addedge(int x,int y){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
}
void dfs(int u,int pre){
	size[u]=0;
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (v==pre)continue;
		dfs(v,u);
		size[u]+=size[v]+2;
		col[u]+=col[v];
		if (col[v])B[u]+=size[v]+2,E[u]+=V[v]+1,Cnt[u]++;
			else W[u]+=size[v]+2;
	}
	if (Cnt[u])V[u]=B[u]+(1.0/Cnt[u])*(E[u]-B[u])+Cnt[u]/(Cnt[u]+1.0)*W[u];
}
void Dfs(int u,int pre,int flag,long double now){
	int cnt=Cnt[u],b=B[u],w=W[u];
	long double exp=E[u];
	if (flag)b+=N-size[u],exp+=now+1,cnt++;
		else w+=N-size[u];
	if (cnt)ans+=b+(1.0/cnt)*(exp-b)+cnt/(cnt+1.0)*w;
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (v==pre)continue;
		if (col[v])b-=size[v]+2,exp-=V[v]+1,cnt--;
			else w-=size[v]+2;
		if (cnt)Dfs(v,u,1,b+(1.0/cnt)*(exp-b)+cnt/(cnt+1.0)*w);
			else Dfs(v,u,col[u]-col[v],0);
		if (col[v])b+=size[v]+2,exp+=V[v]+1,cnt++;
			else w+=size[v]+2;
	}
}
int main(){
	scanf("%d",&n);N=n*2-2;
	for (i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	scanf("%d",&m);
	for (i=1;i<=m;i++){
		scanf("%d",&x);
		col[x]=1;
	}
	dfs(1,0);
	Dfs(1,0,0,0);
	printf("%.10Lf\n",ans/n);
}