Liveddd's Blog

愛にできることはまだあるかい

CF566C Logistical Questions

发表于 更新于 分类于
本文字数： 3.2k 阅读时长 ≈ 7 分钟

大清新妙妙题。

设 $d(x,y)$ 为其在原树上的距离，$dis(x,y)=d(x,y)^{\frac{3}{2}}$。首先我们考虑链上情况，对于 $[a,b]$ 这条路径，随着 $i$ 的移动，容易发现 $dis(x,i)$ 是一个下凸函数，有且仅有一个极值点。我们可以三分求。更进一步，我们发现树上不过是将很多条链拼起来，所以也是若干个下凸函数相加，得到依旧是关于 $x$ 的下凸函数。

于是我们考虑在树上一步一步逼近取到极值的 $x$。一个朴素的想法是，求出当前位置的所有子节点的答案，然后向最小的子节点走。但这样显然是 $\mathcal O(n^2)$，和暴力一个复杂度。不难想到我们可以使用点分治的方式来代替，也就是每次找到子树的重心再按照上面进行。不幸的是，这样还是会被卡成 $\mathcal O(n^2)$ 的。

考虑瓶颈在哪里，因为我们只要计算一个点的贡献就需要遍历整棵树，这样当度数很多时会寄。但是下凸函数的性质我们并没有用好，于是就有了妙妙的做法——对函数求导。对 $dis(x,i)$ 求导，得到 $dis(x,i)’=1.5\cdot d(x,i)^{\frac{1}{2}}$。求出该子节点为根的子树中所有项导函数之和 $dv_i$。那么 $x$ 在向某一个 $son$ 移动时，其余所有点的导数加一，该点导数减一。所以导函数变为 $(\sum_{i} p_i)-2\times p_{son}$，我们只需要找到 $son$ 的导函数 $f(son)’\le 0$ 的点即可（因为有且仅有一个极值点，这样的 $son $ 也是唯一的）。而每次求各个子树的复杂度为 $\mathcal O(n)$。于是总的时间复杂度为 $\mathcal O(n\log n)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<cstdio>
#include<cmath>
using  namespace std;
const int N=2e5+10;
const double INF=1e30;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,anspos,rt;
int v[N],nowtot;
int tot,head[N],ver[N<<1],e[N<<1],ne[N<<1];
int si[N],maxp[N];
bool vis[N];
double ans=INF,sum,dv[N];

inline void add(int u,int v,int w)
{
    ver[++tot]=v;
    e[tot]=w;
    ne[tot]=head[u];
    head[u]=tot;
}
void get_rt(int x,int fa)
{
    if(vis[x])return ;
    si[x]=1;
    
    maxp[x]=0;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa||vis[y])continue;
        get_rt(y,x);
        si[x]+=si[y];
        maxp[x]=max(maxp[x],si[y]);
    }
    
    maxp[x]=max(maxp[x],nowtot-si[x]);
    if(maxp[x]<maxp[rt])rt=x;
}
void calc(int x,int fa,double &dv,int nowd)
{
    sum+=pow(nowd,1.5)*v[x],dv+=1.5*sqrt(nowd)*v[x];
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        calc(y,x,dv,nowd+e[i]);
    }
}
void dfs(int x)
{
    if(vis[x])return ;
    rt=0;
    get_rt(x,0);
    x=rt;
    vis[x]=1;
    sum=0;
    double sumd=0;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        dv[y]=0;
        calc(y,x,dv[y],e[i]);
        sumd+=dv[y];
    }
    if(sum<ans)anspos=x,ans=sum;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(sumd-2*dv[y]<=0)
        {
            nowtot=si[y];
            dfs(y);
            continue;
        }
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)read(v[i]);
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        read(u,v,w);
        add(u,v,w);
        add(v,u,w);
    }
    nowtot=n;
    maxp[0]=n;
    dfs(1);
    printf("%d %lf",anspos,ans);
    return 0;
}