題目
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/206310.html
標籤：其他
下一篇：Java學習筆記_06 回圈結構