题目
https://gmoj.net/senior/#main/show/6842
题解
发现很难将路径分开维护那一坨式子的贡献啊……那就维护整条路径吧！
结论及证明
这题有一个结论： p o w e r , p o i n t power,point power,point越大，新的 p o i n t point point越大。
证明：
p o i n t ′ = p o i n t + 2 sig ( Δ p o w e r ) ( ∣ Δ p o w e r ∣ + 1 − 1 ) − A ⋅ sig ( Δ p o i n t ) ( ∣ Δ p o i n t ∣ + 1 − 1 ) = 2 Δ p o w e r ∣ Δ p o w e r ∣ ( ∣ Δ p o w e r ∣ + 1 − 1 ) − A ⋅ Δ p o i n t ∣ Δ p o i n t ∣ ( ∣ Δ p o i n t ∣ + 1 − 1 ) \begin{aligned} point' &=point+2\operatorname{sig}{(\Delta power)}(\sqrt{|\Delta power|+1}-1)-A\cdot \operatorname{sig}{(\Delta point)}(\sqrt{|\Delta point|+1}-1)\\[2ex] &=2\cfrac{\Delta power}{|\Delta power|}(\sqrt{|\Delta power|+1}-1)-A\cdot \cfrac{\Delta point}{|\Delta point|}(\sqrt{|\Delta point|+1}-1) \end{aligned} point′=point+2sig(Δpower)(∣Δpower∣+1 −1)−A⋅sig(Δpoint)(∣Δpoint∣+1 −1)=2∣Δpower∣Δpower(∣Δpower∣+1 −1)−A⋅∣Δpoint∣Δpoint(∣Δpoint∣+1 −1)
令 f ( x ) = { x ∣ x ∣ ( ∣ x ∣ + 1 − 1 ) , x ≠ 0 0 , x = 0 f(x)=\begin{cases} \cfrac{x}{|x|}(\sqrt{|x|+1}-1),&x\neq 0\\[3ex] 0,&x=0 \end{cases} f(x)=⎩⎪⎪⎨⎪⎪⎧∣x∣x(∣x∣+1 −1),0,x=0x=0
可以用定义法证明 f ( x ) f(x) f(x)是增函数。
那么 p o i n t ′ = p o i n t + 2 f ( Δ p o w e r ) − A ⋅ f ( Δ p o i n t ) = p o i n t 1 + 2 f ( p o w e r 1 − p o w e r 2 ) − A ⋅ f ( p o i n t 1 − p o i n t 2 ) \begin{aligned} point'&=point+2f(\Delta power)-A\cdot f(\Delta point)\\ &=point_1+2f(power_1-power_2)-A\cdot f(point_1-point_2) \end{aligned} point′=point+2f(Δpower)−A⋅f(Δpoint)=point1+2f(power1−power2)−A⋅f(point1−point2)
当 A = 0 A=0 A=0时，由于 p o w e r 2 power_2 power2是定值，因此 p o w e r 1 power_1 power1越大 p o i n t ′ point' point′越大，得证。
现在考虑 A = 1 A=1 A=1的情况。
令 g ( x ) = x − f ( x ) g(x)=x-f(x) g(x)=x−f(x)。可以发现它也是一个增函数。
p o i n t ′ = p o i n t 1 + 2 f ( p o w e r 1 − p o w e r 2 ) − f ( p o i n t 1 − p o i n t 2 ) = p o i n t 1 − p o i n t 2 + 2 f ( p o w e r 1 − p o w e r 2 ) − f ( p o i n t 1 − p o i n t 2 ) + p o i n t 2 = p o i n t 2 + 2 f ( p o w e r 1 − p o w e r 2 ) + g ( p o i n t 1 − p o i n t 2 ) \begin{aligned} point'&=point_1+2f(power_1-power_2)-f(point_1-point_2)\\[2ex] &=point_1-point_2+2f(power_1-power_2)-f(point_1-point_2)+point_2\\[2ex] &=point_2+2f(power_1-power_2)+g(point_1-point_2) \end{aligned} point′=point1+2f(power1−power2)−f(point1−point2)=point1−point2+2f(power1−power2)−f(point1−point2)+point2=point2+2f(power1−power2)+g(point1−point2)
由 f ( x ) , g ( x ) f(x),g(x) f(x),g(x)的单调性可以得出结论。
下面是 f ( x ) , g ( x ) f(x),g(x) f(x),g(x)的图像：
做法
有了这个结论，就可以愉快地二分答案+树上DP啦！
对于目前二分出来的 p o w e r 1 power_1 power1，考虑怎么在树上得到最大的 p o i n t point point。
可以设 f i f_i fi表示 i 的子树中，从某个叶子节点进来，走到 i 时的最大 p o i n t point point（上面已经证明了 p o i n t point point越大越好，因此很容易转移）
接着 O ( n ) O(n) O(n)旋根就好了，注意判断从同一个叶子节点进出的情况。
CODE
#include<cmath>
#include<cstdio>
using namespace std;
typedef long double LF;
#define inf 500000
#define M 200005
#define N 100005
#define e 1e-8
int fir[N],to[M],nex[M],a[N],b[N],deg[N],son[N][2],A,p0,p1,s;
//a:power; b:point
LF f[N],g[N][2],maxx,P;
inline void inc(int x,int y)
{
++deg[x],++deg[y];
to[++s]=y,nex[s]=fir[x],fir[x]=s;
to[++s]=x,nex[s]=fir[y],fir[y]=s;
}
inline int sig(LF x){ return x==0?0:(x<0?-1:1);}
inline LF calc(int k,LF power,LF point)
{ return 2*sig(power-a[k])*(sqrt(abs(power-a[k])+1)-1)-A*sig(point-b[k])*(sqrt(abs(point-b[k])+1)-1);}
void dfs(int k,int fa)
{
g[k][0]=g[k][1]=-inf,son[k][0]=son[k][1]=0;
if(k>1&°[k]==1) return;
for(int i=fir[k];i;i=nex[i]) if(to[i]!=fa)
{
dfs(to[i],k);
if(f[to[i]]>g[k][0])
g[k][1]=g[k][0],son[k][1]=son[k][0],
g[k][0]=f[to[i]],son[k][0]=to[i];
else if(f[to[i]]>g[k][1]) g[k][1]=f[to[i]],son[k][1]=to[i];
}
f[k]=g[k][0]+calc(k,P,g[k][0]);
}
void rotate(int k,int fa)
{
if(deg[k]==1&&f[k]>maxx) maxx=f[k];
LF gk[2],sk[2],fk=f[k],gi[2],si[2],fi;
gk[0]=g[k][0],sk[0]=son[k][0];
gk[1]=g[k][1],sk[1]=son[k][1];
for(int i=fir[k];i;i=nex[i]) if(to[i]!=fa)
{
gi[0]=g[to[i]][0],si[0]=son[to[i]][0];
gi[1]=g[to[i]][1],si[1]=son[to[i]][1],fi=f[to[i]];
if(to[i]==son[k][0]) f[k]=deg[k]==1?p0+calc(k,P,p0):g[k][1]+calc(k,P,g[k][1]);
if(f[k]>g[to[i]][0])
{
g[to[i]][1]=g[to[i]][0],son[to[i]][1]=son[to[i]][0];
g[to[i]][0]=f[k],son[to[i]][0]=k;
f[to[i]]=f[k]+calc(to[i],P,f[k]);
}
else if(f[k]>g[to[i]][1]) g[to[i]][1]=f[k],son[to[i]][1]=k;
rotate(to[i],k);
g[to[i]][0]=gi[0],son[to[i]][0]=si[0];
g[to[i]][1]=gi[1],son[to[i]][1]=si[1];
g[k][0]=gk[0],son[k][0]=sk[0];
g[k][1]=gk[1],son[k][1]=sk[1];
f[k]=fk,f[to[i]]=fi;
}
}
int main()
{
freopen("pigeatyy.in","r",stdin);
freopen("pigeatyy.out","w",stdout);
LF l=-inf,r=inf,mid,ans=0;
int test,n,x,y;
scanf("%d%d%d%d%d",&test,&n,&p0,&p1,&A);
for(int i=1;i<n;++i) scanf("%d%d",&x,&y),inc(x,y);
for(int i=1;i<=n;++i) scanf("%d%d",a+i,b+i);
while(l<=r)
{
mid=(l+r)/2;
if(n==1) maxx=p0+calc(1,mid,p0);
else
{
for(int i=1;i<=n;++i)
if(deg[i]==1)
{
f[i]=p0+calc(i,mid,p0);
if(f[i]>=p1){ r=mid-e,ans=mid;continue;}
}
else f[i]=0;
P=mid,dfs(1,0);
maxx=0,rotate(1,0);
}
if(maxx>=p1) r=mid-e,ans=mid;
else l=mid+e;
}
printf("%.6LF\n",ans);
return 0;
}
