「雅礼集训 2018-04-03」Problem C

发表于

给出一棵 NN 个点的有根树，这棵树以 11 号节点为根。现在你需要对于每个非叶子节点 YY 选择它的一个儿子 XX ，并把连接 X,YX,Y 的边标记为重边，其它的边为轻边。对于这棵树的每个叶子节点，把它到根节点经过的边依次写下来，一条轻边的代价为 11 ，一段连续的重边代价为 ⌊log2L+1⌋\left \lfloor log_2L+1 \right \rfloor ，LL 为这段重边的数量，这个叶子的代价等于这些代价之和。求出在最优情况下，所有叶子的代价中的最大值最小是多少。

Constraints

n≤2⋅105n \leq 2\cdot 10^5

Solution

记一下 O(n2)O(n^{2}) 的暴力……正解把复杂度优化到了 O(nlogn)O(nlogn) ，至今仍然不是很理解。

令 gig_{i} 表示节点 ii 的子树里到 ii 代价最大的叶子节点的代价，每一次贪心的选择 gig_{i} 最大的儿子节点作为重儿子。

因为贡献不方便计算，令 f(i,k)f(i,k) 表示在节点 ii 有一条向上长度为 kk 的重链时的答案，则可得：

f(i,k)=max(f(heavy,k+1),g(light)+⌈log2k+1⌉+1)f(i,k)=max(f(heavy,k+1),g(light)+\lceil log_{2}k+1\rceil +1)

下面的是正解的代码。

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
const int inf=0x3f3f3f3f;
int T,n,x,y,cnt;
int first[N],g[N],f[N][20];
struct edge{int to,next;}e[N<<1];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
void dfs(int x,int fa)
{
    int mx=-inf,elmx=-inf,son=0;
    for(int i=first[x];i;i=e[i].next)
    {
        int to=e[i].to;
        if(to==fa)continue;
        dfs(to,x);
        if(g[to]>mx)elmx=mx,mx=g[to],son=to;
        else if(g[to]>elmx)elmx=g[to];
    }
    if(mx<0)
    {
        g[x]=0;f[x][0]=0;
        for(int i=1;i<18;i++)f[x][i]=1<<(i-1);
        return;
    }
    elmx++;
    if(f[son][0])g[x]=mx;else g[x]=mx+1;
    g[x]=max(g[x],elmx);
    for(int i=0;i<18;i++)
    {
        int v=g[x]+i;
        if(v==elmx)f[x][i]=0;
        else f[x][i]=1<<min(20,v-elmx-1);
        if(v-mx<18)f[x][i]=min(f[x][i],f[son][v-mx]-1);
    }
}
void work()
{
    cnt=0;memset(first,0,sizeof(first));
    n=read();
    for(int i=1;i<n;i++)
        x=read(),y=read(),ins(x,y),ins(y,x);
    dfs(1,0);printf("%d\n",g[1]);
}
int main()
{
    T=read();
    while(T--)work();
    return 0;
}