CF1606F Tree Queries

记一个看似暴力但是比较巧妙的解法。

设 $f_{x,k}$ 表示当删点代价为 $k$，以 $x$ 为根的子树能得到的答案。容易列出状态转移方程 $f_{x,k}\gets \max(1,f_{y,k}-k)$。直接做是 $\mathcal O(n^2)$ 的。显然 $f_{y,k}>k$ 的时候节点 $y$ 才可能被选择。所以当 $k$ 越大时，有用的状态更少。

固定 $k$ 来研究有用的状态数。我们根据状态的转移将原树划分成若干棵森林。这些森林除了叶子之外，其它都是有用的状态。考虑森林中任意一个大小为 $m$ 的树。仔细观察每从叶子往上走，每有一个有用状态答案都会减少 $k$。那么有用的状态数最多为 $\lfloor \frac{m}{k} \rfloor$，对于原树而言有用的状态数就最多为 $\lfloor \frac{n}{k} \rfloor$。那么对于所有的 $k$，有用的状态数的总和为 $\displaystyle \sum_{k=1}^n \lfloor n/k \rfloor$，这就是个调和级数。于是总的状态数为 $\mathcal O(n\ln n)$。

于是我们直接暴力 DP 就好了，过程中只保留有用的状态即可。时间复杂度与空间复杂度均为 $\mathcal O(n\ln n)$。

Code

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool 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,q;
int tot,head[N],ver[N<<1],ne[N<<1];
int cnt[N],si[N];
vector<int>f[N];
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs(int x,int fa)
{
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        si[x]++;
        cnt[x]=max(cnt[x],cnt[y]);
    }
    cnt[x]=max(cnt[x],si[x]-1);
    f[x].resize(cnt[x]+1);
    
    for(int i=0;i<=cnt[x];i++)f[x][i]=si[x];
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        for(int j=0;j<=cnt[y];j++)
            f[x][j]+=max(0,f[y][j]-j-1);
    }
    int i=0;
    while(i<cnt[x]&&f[x][i]>=i+1)i++;
    cnt[x]=i;
}
int main()
{
    read(n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u,v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    read(q);
    while(q--)
    {
        int x,k;
        read(x,k);
        if(k<=f[x].size()-1)printf("%d\n",f[x][k]);
        else printf("%d\n",si[x]);
    }
    return 0;
}