【JZOJ3987】Tree 题解

题目大意

  $N \le 5000$
  $V, T < LIMIT \le 10^5$

【测试点1~3】N<=2000， T=0

  暴力。

【测试点4~6】N<=2000， LIMIT, T<=100

  先枚举 C。

  求平均肯定先二分，二分完之后相当于要选一些路径，然后每条路径减去一个值，最后判断是否大于一个值。
  设 $f_{i,0/1/2}$ 表示：以 i 为根的子树，0 表示点 i 不选，1 表示点 i 选了并且将来还要往上走，2 表示点 i 选了并且将来不往上走（即有条路径在点 i 处转弯）
  转移比较显然。

【测试点7~12】N<=1000， LIMIT, T<=10^5

  发现 C 不能枚举了。
  可是，比如我现在有个 C，而所有的 V[i]+C 都不等于 LIMIT-1，那就说明我这个 C 肯定不是最优的。
  因此有用的 C 最多只有 N 个。

  dp照常。

【测试点13~20】N<=5000

  上述方法被卡常了。
  优化1：对于每个 C （已经最多 N 个了），在做二分之前先假设 mid 是当前的 ans，用二分的判断函数判断一下是否可行，若不可行则continue。这样可以去掉很多无用的二分。
  优化2：用随机大法打乱 C 的枚举顺序，据说这样期望变成了 $O(n \log n)$。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int maxn=5005, maxL=1e5+5;
const double eps=1e-8;

int n,L,v[maxn],T;

int tot,go[2*maxn],next[2*maxn],f1[maxn];
void ins(int x,int y)
{
	go[++tot]=y;
	next[tot]=f1[x];
	f1[x]=tot;
}

double f[maxn][3],g[maxn],Mid;
void dfs(int k,int last,int c)
{
	double rl=((v[k]+c)%L)/Mid, fir=0, sec=0, sum=0;
	for(int p=f1[k]; p; p=next[p]) if (go[p]!=last)
	{
		dfs(go[p],k,c);
		sum+=g[go[p]];
		double t=f[go[p]][1]-g[go[p]];
		if (t-fir>eps)
		{
			sec=fir;
			fir=t;
		} else if (t-sec>eps) sec=t;
	}
	f[k][0]=sum;
	f[k][1]=sum+fir+rl;
	f[k][2]=sum+fir+sec+rl;
	g[k]=max(f[k][0],max(f[k][1]-1,f[k][2]-1));
}

bool check(double mid,double c)
{
	Mid=mid;
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	dfs(1,0,c);
	return (g[1]>1);
}

int vt[maxn],vt0;//存可能的C
bool bz[maxL];
int main()
{
	srand(101);
	
	scanf("%d %d",&n,&L);
	fo(i,1,n) scanf("%d",&v[i]);
	fo(i,1,n-1)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		ins(x,y), ins(y,x);
	}
	scanf("%d",&T);
	
	vt[++vt0]=0;
	vt[++vt0]=T;
	fo(i,1,n)
	{
		v[i]%=L;
		if (L-1-v[i]<=T && !bz[v[i]]) vt[++vt0]=L-1-v[i], bz[v[i]]=1;
	}
	random_shuffle(vt+1,vt+1+vt0);//优化2
	
	double ans=0;
	fo(ci,1,vt0)
	{
		if (!check(ans,vt[ci])) continue;//优化1
		
		double l=0, r=(double)n*(L-1);
		while (l+eps<=r)
		{
			double mid=(l+r)/2;
			
			if (check(mid,vt[ci])) l=mid+eps; else r=mid-eps;
		}
		ans=max(ans,l-eps);
	}
	
	printf("%.7f\n",ans);
}