博客

题目描述

“What’s left to do when we’ve lost all hope?”

“若内心万念俱灰，是否注定无心行挽？”

——来自网易云音乐

不必做好输掉一切的准备。

所以，无畏结局。

在尽头，已经不能再做什么，来挽回。

在尽头，所有的一切都走向简化，没有了重复，没有了错杂，只剩下一片废墟。

就是说，世界曾是一副错杂的无向图，而在尽头，它已成为一个没有环的无向连通图，也就是说已成为一棵树。

这棵树有n个节点，有n-1条边，每条边的长度都是1。

给出q组询问，每组询问会给出k个关键点，设f(u)表示所有关键点中离点u最近的关键点离u的距离，求出最大的f(u)

虚树

把关键点的虚树做出来。

然后随便做。

……

如果这么写会被打死QAQ

大概啊就是，你讨论u在哪里：

1、不在虚树根的子树里。

在原树中树形DP出一个点不往子树里走的最长路。在虚树中树形DP出一个点子树里关键点到它的最短路。

2、在虚树上一个点的儿子子树中，且这些儿子不包含在虚树路径上的儿子。

在原树中树形DP出一个点往子树里走的最长路。对于每个点开set保存每个儿子子树的这个最长路信息。在虚树上删除掉对应儿子找到往里走的最大值。同时你还需要在虚树中树形DP出离它最近的关键点到它的距离。

3、在虚树路径及延伸子树中。

在虚树中树形DP出一个点子树里最近的关键点距离以及除去一颗子树其余部分关键点到这个的父亲的最近距离。

枚举虚树一条边，然后直接距离/2，xjb讨论一下，就是你知道分界点，然后分两段查询。

这些链查询都可以用倍增，注意这个倍增要分上下并和深度挂钩。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=100000+10;
multiset<int> s[maxn];
multiset<int>::iterator it;
int h[maxn],go[maxn*2],next[maxn*2],dep[maxn],dfn[maxn],zjy[maxn];
int h2[maxn],g2[maxn],n2[maxn],a[maxn*2];
int f1[maxn],f2[maxn],w1[maxn],w2[maxn],g[maxn],gg[maxn];
int ff1[maxn],ff2[maxn],ww1[maxn],ww2[maxn],ggg[maxn];
int f[maxn][22],fa[maxn],b1[maxn][22],b2[maxn][22];
bool pd[maxn];
int i,j,k,l,t,n,m,tot,top,cnt,ans,root;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void add(int x,int y){
    go[++tot]=y;
    next[tot]=h[x];
    h[x]=tot;
}
void add2(int x,int y){
    g2[++cnt]=y;
    n2[cnt]=h2[x];
    h2[x]=cnt;
}
void dfs(int x,int y){
    dfn[x]=++top;
    dep[x]=dep[y]+1;
    f[x][0]=y;
    int t=h[x];
    f1[x]=f2[x]=0;
    while (t){
        if (go[t]!=y){
            dfs(go[t],x);
            s[x].insert(f1[go[t]]);
            if (f1[go[t]]+1>f1[x]){
                f2[x]=f1[x];
                w2[x]=w1[x];
                f1[x]=f1[go[t]]+1;
                w1[x]=go[t];
            }
            else if (f1[go[t]]+1>f2[x]){
                f2[x]=f1[go[t]]+1;
                w2[x]=go[t];
            }
        }
        t=next[t];
    }
}
void dg(int x,int y){
    if (x==1) g[x]=gg[x]=0;
    else{
        g[x]=g[y]+1;
        if (w1[y]!=x) g[x]=max(g[x],f1[y]+1);
        else g[x]=max(g[x],f2[y]+1);
        if (w1[y]!=x) gg[x]=f1[y];else gg[x]=f2[y];
    }
    int t=h[x];
    while (t){
        if (go[t]!=y) dg(go[t],x);
        t=next[t];
    }
}
void bfs(int x,int y){
    fa[x]=y;
    int t=h2[x];
    ff1[x]=ff2[x]=n;
    while (t){
        if (g2[t]!=y){
            bfs(g2[t],x);
            if (ff1[g2[t]]+dep[g2[t]]-dep[x]<ff1[x]){
                ff2[x]=ff1[x];
                ww2[x]=ww1[x];
                ff1[x]=ff1[g2[t]]+dep[g2[t]]-dep[x];
                ww1[x]=g2[t];
            }
            else if (ff1[g2[t]]+dep[g2[t]]-dep[x]<ff2[x]){
                ff2[x]=ff1[g2[t]]+dep[g2[t]]-dep[x];
                ww2[x]=g2[t];
            }
        }
        t=n2[t];
    }
    if (pd[x]) ff1[x]=ww1[x]=0;
}
void bg(int x,int y){
    if (x==1) ggg[x]=n;
    else{
        ggg[x]=n;
        if (fa[y]) ggg[x]=min(ggg[x],ggg[y]+dep[y]-dep[fa[y]]);
        if (ww1[y]!=x) ggg[x]=min(ggg[x],ff1[y]);
        else ggg[x]=min(ggg[x],ff2[y]);
    }
    //if (pd[x]) ggg[x]=0;
    int t=h2[x];
    while (t){
        if (g2[t]!=y) bg(g2[t],x);
        t=n2[t];
    }
}
bool cmp(int x,int y){
    return dfn[x]<dfn[y];
}
int lca(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    if (dep[x]!=dep[y]){
        int j=zjy[dep[x]];
        while (j>=0){
            if (dep[f[x][j]]>=dep[y]) x=f[x][j];
            j--;
        }
    }
    if (x==y) return x;
    int j=zjy[dep[x]];
    while (j>=0){
        if (f[x][j]!=f[y][j]){
            x=f[x][j];
            y=f[y][j];
        }
        j--;
    }
    return f[x][0];
}
int getfa(int x,int y){
    if (y<0) return -1;
    int j=zjy[dep[x]];
    while (j>=0){
        if (y>=(1<<j)){
            x=f[x][j];
            y-=(1<<j);
        }
        j--;
    }
    return x;
}
int getb1(int x,int y){
    int j=zjy[dep[x]],t=0,l=0;
    while (j>=0){
        if (y>=(1<<j)){
            t=max(t,b1[x][j]+l);
            l+=(1<<j);
            y-=(1<<j);
            x=f[x][j];
        }
        j--;
    }
    return t;
}
int getb2(int x,int y){
    int j=zjy[dep[x]],t=-n;
    while (j>=0){
        if (y>=(1<<j)){
            t=max(t+(1<<j),b2[x][j]);
            y-=(1<<j);
            x=f[x][j];
        }
        j--;
    }
    return t;
}
void solve(int x){
    int t=h2[x],l,j,y,z,w;
    while (t){
        y=getfa(g2[t],dep[g2[t]]-dep[x]-1);
        s[x].erase(s[x].find(f1[y]));
        t=n2[t];
    }
    it=s[x].end();
    if (it!=s[x].begin()){
        it--;
        ans=max(ans,min(ff1[x],ggg[x]+dep[x]-dep[fa[x]])+*it+1);
    }
    t=h2[x];
    while (t){
        y=getfa(g2[t],dep[g2[t]]-dep[x]-1);
        s[x].insert(f1[y]);
        t=n2[t];
    }
    t=h2[x];
    while (t){
        y=g2[t];
        //j=ggg[y]-(dep[y]-dep[x]);
        j=ggg[y];
        l=(j+ff1[y]+dep[y]-dep[x])/2;
        //if (l>ff1[y]&&l<ff1[y]+dep[y]-dep[x]){
            if (l>ff1[y]){
                z=getfa(y,min(l-ff1[y]-1,dep[y]-dep[x]-2));
                if (z!=-1) ans=max(ans,ff1[y]+1+getb1(y,dep[y]-dep[z]+1));
            }
            if (l<ff1[y]+dep[y]-dep[x]-1){
                z=getfa(y,max(l-ff1[y],0));
                w=getfa(y,dep[y]-dep[x]-2);
                if (z!=-1&&w!=-1) ans=max(ans,j+1+getb2(z,dep[z]-dep[w]+1));
            }
        //}
        t=n2[t];
    }
    t=h2[x];
    while (t){
        solve(g2[t]);
        t=n2[t];
    }
}
int main(){
    freopen("do.in","r",stdin);freopen("do.out","w",stdout);
    n=read();m=read();
    fo(i,1,n-1){
        j=read();k=read();
        add(j,k);add(k,j);
    }
    dfs(1,0);
    dg(1,0);
    fo(i,1,n) zjy[i]=floor(log(i)/log(2));
    fo(i,1,n) b1[i][0]=b2[i][0]=gg[i];
    fo(j,1,zjy[n])
        fo(i,1,n){
            f[i][j]=f[f[i][j-1]][j-1];
            b1[i][j]=max(b1[i][j-1],b1[f[i][j-1]][j-1]+(1<<(j-1)));
            b2[i][j]=max(b2[i][j-1]+(1<<(j-1)),b2[f[i][j-1]][j-1]);
        }
    while (m--){
        k=read();
        fo(i,1,k) a[i]=read(),pd[a[i]]=1;
        sort(a+1,a+k+1,cmp);
        top=k;
        fo(i,1,k-1) a[++top]=lca(a[i],a[i+1]);
        //a[++top]=1;
        sort(a+1,a+top+1,cmp);
        top=unique(a+1,a+top+1)-a-1;
        sort(a+1,a+top+1,cmp);
        root=a[1];
        cnt=0;
        fo(i,2,top) add2(lca(a[i-1],a[i]),a[i]);
        bfs(root,0);
        bg(root,0);
        ans=g[root]+ff1[root];
        solve(root);
        printf("%d\n",ans);
        fo(i,1,top) h2[a[i]]=pd[a[i]]=0;
    }
}