Codeforces 526G. Spiders Evil Plan 题解

题目链接：G. Spiders Evil Plan

题目大意：洛谷

题解：首先，\(y\) 条路径可以覆盖 \(2y\) 个叶子，并且容易证明其中一定有一个叶子是直径的一个端点，所以我们以两个直径的端点分别为根建树，然后从大向小取，然后考虑两种调整方案，就可以了。

可以直接拿长链剖分 + 倍增维护。

时间复杂度 \(O(n\log n)\)。

#include 
#include 
#include 
#include 
using namespace std;
const int Maxn=100000;
int n,q;
int head[Maxn+5],arrive[Maxn<<1|5],val[Maxn<<1|5],nxt[Maxn<<1|5],tot;
void add_edge(int from,int to,int w){
    arrive[++tot]=to;
    val[tot]=w;
    nxt[tot]=head[from];
    head[from]=tot;
}
struct Tree{
    int mx_dis,root;
    int dis[Maxn+5],max_dis[Maxn+5],dep[Maxn+5];
    int fa[17][Maxn+5],son[Maxn+5],top[Maxn+5],len[Maxn+5];
    vector v[Maxn+5];
    void init_dfs_1(int u){
        dep[u]=dep[fa[0][u]]+1;
        for(int i=1;fa[i-1][fa[i-1][u]];i++){
            fa[i][u]=fa[i-1][fa[i-1][u]];
        }
        max_dis[u]=dis[u];
        if(mx_dis==0||dis[mx_dis]len[q];
    }
    int init(int x){
        mx_dis=0;
        dis[x]=0;
        init_dfs_1(x);
        root=mx_dis;
        memset(dis,0,sizeof dis);
        memset(fa,0,sizeof fa);
        memset(dis,0,sizeof dis);
        memset(son,0,sizeof son);
        mx_dis=0;
        init_dfs_1(root);
        init_dfs_2(root,root);
        len[root]=max_dis[root];
        for(int i=1;i<=n;i++){
            if(top[i]==i){
                s[++c]=i;
            }
        }
        sort(s+1,s+1+c,[&](int p,int q){return len[p]>len[q];});
        for(int i=1;i<=c;i++){
            ans[i]=ans[i-1]+len[s[i]];
            for(int u=s[i];u;u=son[u]){
                col[u]=i;
            }
        }
        return root;
    }
    int find_ans(int x,int y,int *a){
        int u=x;
        for(int i=16;i>=0;i--){
            if(col[fa[i][u]]>y){
                u=fa[i][u];
            }
        }
        u=fa[0][u];
        return ans[y]+max_dis[x]-a[u];
    }
    int query(int x,int y){
        y=(y<<1)-1;
        if(y>=c){
            return ans[c];
        }
        if(col[x]<=y){
            return ans[y];
        }
        return max(find_ans(x,y-1,dis),find_ans(x,y,max_dis));
    }
}tree_1,tree_2;
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i