lyzlyz?lyzlyz!

发现这套题去年暑假做过！

然而依然没有思路。。。

这真是一个伤心的故事。

T1

鉴于BZOJ爆炸的先例，先描述下题面。

给你一棵树，支持：1、修改某个点的权值。2、求点权和最大的一个联通块。

我记得这是道树剖。

然而我只会n²的树形dp和一条链的情况。

%%%小条将此题AC

令dp[u]表示必须选u，u及u的轻儿子构成的子树的最大联通块的点权。

那么只要对于重链上的dp值求最大连续子段和即可得出最终答案。

对于修改，显然只会对top[u]产生影响，那么需要求出点权修改前后的差值来进行修改。

然后不断地更新top即可。

T2

询问n个点n条边的简单无向连通图的个数。

OEIS神题。

通过查询可以获得通项公式：

[tex]\frac{(n-1)!*n^n}{2}*\sum^{n}_{k=3}\frac{1}{(n-k)!*n^k}[/tex]

然后就解决了。（然而在一堆蚂蚁文中我已经彻底晕了）

T3

给出n个白点，每次随机选出一个区间并将区间内的白点染黑，问将白点全部染黑的期望步数。

直接30分状压保平安。。。

当然还有另外一种开黑方法：按照题意随机1亿次取平均值。

令p[i]为i次没有全部染黑的概率。

[tex]ans=\sum^{\infty}_{i=0}p[i][/tex]

没有染黑，必然留下一些白点，不妨设它们的编号分别是a₁,a₂,……,a_n。

那么只能在[1,a₁-1],[a₁+1,a₂-1],……,[a_n-1+1,a_n]中选择。

若这些区间的子区间有A个，对P[i]的贡献就是：

[tex]p=(\frac{2A}{(n+1)*n})^i[/tex]

显然需要容斥，如果白点有奇数个对答案的贡献就是正的，否则就是负的。

对于最终答案的统计，有：

[tex]\sum^{\infty}_{i=0}P[i]=\frac{1}{1-p}[/tex]

那么只要通过dp来求出p就可以了！

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=800010;
const int inf=1000000007;
int n,m,i,x,y,ch,opt,edgenum,time,cnt;
int a[M],head[M],vet[M],next[M],flag[M],fa[M],size[M],son[M],top[M],tid[M],space[M],dp[M];
struct node{ll w,l,r,mx;}tree[M];
void addedge(int x,int y){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
}
void dfs(int u,int pre){
	size[u]=1;fa[u]=pre;
	dp[u]=a[u];
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (v==pre)continue;
		dfs(v,u);
		if (dp[v]>0)dp[u]+=dp[v];
		size[u]+=size[v];
		if (!son[u]||size[v]>size[son[u]])son[u]=v;
	}
}
void Dfs(int u,int ance){
	flag[u]=1;
	tid[u]=++time;top[u]=ance;
	if (son[u]){
		if (dp[son[u]]>0)dp[u]-=dp[son[u]];
		Dfs(son[u],ance);
	}
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (flag[v])continue;
		space[++cnt]=++time;
		Dfs(v,v);
	}
}
void pushup(int p){
	int l=p<<1,r=p<<1^1;
	tree[p].w=tree[l].w+tree[r].w;
	tree[p].l=max(tree[l].l,tree[l].w+tree[r].l);
	tree[p].r=max(tree[r].r,tree[r].w+tree[l].r);
	tree[p].mx=max(max(tree[p].l,tree[p].r),max(max(tree[l].mx,tree[r].mx),tree[l].r+tree[r].l));
}
void update(int x,int l,int r,int p,int t){
	if (l==r){
		tree[p].w=t;
		tree[p].l=max(t,0);
		tree[p].r=max(t,0);
		tree[p].mx=max(t,0);
		return;
	}
	int mid=l+r>>1;
	if (x<=mid)update(x,l,mid,p<<1,t);
		else update(x,mid+1,r,p<<1^1,t);
	pushup(p);
}
ll Search(int x,int y,int l,int r,int p){
	if (x==l&&y==r)return tree[p].w;
	int mid=l+r>>1;
	if (y<=mid)return Search(x,y,l,mid,p<<1);
		else if (x>mid)return Search(x,y,mid+1,r,p<<1^1);
			else return Search(x,mid,l,mid,p<<1)+Search(mid+1,y,mid+1,r,p<<1^1);
}
ll search(int x,int y,int l,int r,int p){
	if (x==l&&y==r)return tree[p].l;
	int mid=l+r>>1;
	if (y<=mid)return search(x,y,l,mid,p<<1);
		else if (x>mid)return search(x,y,mid+1,y,p<<1^1);
			else return max(search(x,mid,l,mid,p<<1),search(mid+1,y,mid+1,r,p<<1^1)+Search(x,mid,l,mid,p<<1));
}
void Update(int x,int y){
	ll p=search(tid[top[x]],time,1,time,1);
	update(tid[x],1,time,1,dp[x]+y);
	dp[x]+=y;
	ll q=search(tid[top[x]],time,1,time,1);
	if (top[x]!=1)Update(fa[top[x]],q-p);
}
int main(){
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)scanf("%d",&a[i]);
	for (i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	dfs(1,-1);
	Dfs(1,1);
	for (i=1;i<=cnt;i++)update(space[i],1,time,1,-inf);
	for (i=1;i<=n;i++)update(tid[i],1,time,1,dp[i]);
	for (i=1;i<=m;i++){
		scanf("%d",&opt);
		if (opt==1){
			scanf("%d%d",&x,&y);
			Update(x,y-a[x]);
			a[x]=y;
		}else printf("%d\n",tree[1].mx);
	}
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i;
struct bignum{int w[5010];}yi,now,cnt,ans;
bignum operator + (bignum a,bignum b){
	bignum c;
	int l=max(a.w[0],b.w[0]);
	//for (int i=0;i<=l;i++)c.w[i]=0;
	memset(c.w,0,sizeof c.w);
	for (int i=1;i<=l;i++){
		c.w[i+1]=c.w[i+1]+(a.w[i]+b.w[i]+c.w[i])/10000;
		c.w[i]=(a.w[i]+b.w[i]+c.w[i])%10000;
	}
	if (c.w[l+1])c.w[0]=l+1;else c.w[0]=l;
	return c;
}
bignum operator - (bignum a,int b){
	a.w[1]-=b;
	int now=1;
	while (a.w[now]<0)a.w[now+1]-=1,a.w[now]+=10000,now++;
	while (a.w[0]&&!a.w[a.w[0]])a.w[0]--;
	return a;
}
bignum operator * (bignum a,bignum b){
	bignum c;
	//for (int i=0;i<=a.w[0]+b.w[0];i++)c.w[i]=0;
	memset(c.w,0,sizeof c.w);
	for (int i=1;i<=a.w[0];i++)
		for (int j=1;j<=b.w[0];j++){
			c.w[i+j]=c.w[i+j]+(a.w[i]*b.w[j]+c.w[i+j-1])/10000;
			c.w[i+j-1]=(a.w[i]*b.w[j]+c.w[i+j-1])%10000;
		}
	if (c.w[a.w[0]+b.w[0]])c.w[0]=a.w[0]+b.w[0];else c.w[0]=a.w[0]+b.w[0]-1;
	return c;
}
bignum operator / (bignum a,int b){
	for (int i=a.w[0];i>1;i--){
		a.w[i-1]=a.w[i-1]+a.w[i]%b*10000;
		a.w[i]=a.w[i]/b;
	}
	a.w[1]=a.w[1]/b;
	while (a.w[0]&&!a.w[a.w[0]])a.w[0]--;
	return a;
}
void print(bignum a){
	printf("%d",a.w[a.w[0]]);
	for (int i=a.w[0]-1;i;i--)
		if (a.w[i]>=1000)printf("%d",a.w[i]);
			else if (a.w[i]>=100)printf("0%d",a.w[i]);
				else if (a.w[i]>=10)printf("00%d",a.w[i]);
					else printf("000%d",a.w[i]);
	puts("");
}
int main(){
	scanf("%d",&n);
	if (n<=2){puts("0");return 0;}
	yi.w[0]=1;yi.w[1]=1;
	now.w[0]=cnt.w[0]=ans.w[0]=1;
	for (i=1;i<n;i++)now=now+yi;
	cnt=now,now=now+yi;
	int N=n-2;
	bignum Now=now;
	while (N){
		if (N&1)cnt=cnt*Now;
		Now=Now*Now;
		N>>=1;
	}
	cnt=cnt/2;
	now=now-2;
	for (i=3;i<=n;i++){
		cnt=cnt/n*now;
		now=now-1;
		ans=ans+cnt;
	}
	print(ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,j,k;
double ans;
double dp[110][10010];
int main(){
	scanf("%d",&n);
	int m=(n+1)*n/2;
	dp[0][0]=1;
	for (i=1;i<=n+1;i++)
		for (j=i;j>=0;j--)
			for (k=(i-j)*(i-j-1)/2;k<=m;k++)dp[i][k]-=dp[j][k-(i-j)*(i-j-1)/2];
	for (i=0;i<m;i++)ans+=dp[n+1][i]/(1-(double)i/m);
	printf("%.4lf\n",ans);
}