NC13950 Alliances题解

题目描述：

一颗 $n$ 个节点的树。给定 $k$ 个点集（ $k$ 个帮派），编号为 $1-k$ 。第i个点集代表第i个帮派占据的点的集合。
定义一个节点被占领当且仅当满足下面其中一个条件：

该结点被一个帮派所占据。
该结点位于被占领的两个结点的路径上。

Q个询问，每个询问给出一个点 $V$ ，一个数 $cnt$ ，和 $cnt$ 个数（ $t_1,t_2 ... t_c$ ），代表在这个询问中选取（ $t_1,t_2...t_c$ ）这 $cnt$ 个帮派，在此次询问中只考虑这 $cnt$ 个帮派，问结点V距最近的一个被占领的结点的距离。

数据范围：1≤n,k,Q≤500000, 1≤每个帮派占据城市数之和≤500000, 1≤每个询问中考虑的帮派数之和≤500000
建议好好读一下原题目，涉及的量比较多。不是很好理解。

题目分析：

麻烦的一道题。
为了解决这个题，首先需要搞清楚被“占领”的结点有什么样的特点。
取任意一点为整颗树的根结点。
根据题目的描述，如果结点 $u$ , $v$ 都被占据，那么从u到v的路径上的点都被占领。可以得出LCA(u,v)被占领，并且被占领的点都位于LCA(u,v)到u的路径上和LCA(u,v)到v的路径上。
猜想：

若点 $v_1,v_2...v_n$ 被占据，那么所有被占领的点为 $LCA（v_1,v_2...v_n）$ 到点 $v_1,v_2...v_n$ 的路径上所有点的集合

这个猜想是可以利用LCA的性质证明的，下面简单的说明一下：

设 $p=LCA（v_1,v_2...v_n）$ ,那么点 $v_1,v_2...v_n$ 都位于以 $p$ 为根的子树上，并且至少有 $2$ 个以 $p$ 的孩子结点为根的树上有被占据的点。（即 $v_1,v_2...v_n$ 至少在结点 $p$ 延伸出的两个分支上），否者与LCA的定义矛盾。这样就对于一个被占据的点v,一定存在一个 $u$ （在另一个分支上找）， $p$ 位于从 $v$ 到 $u$ 的路径上，那么 $p$ 到 $v$ 的路径上都是被占领的点。
同样也可以证明所有的点都在这样的路径上

这个证明还需要补充一些细节，不过对于理解这个题来说已经足够了

这个结论是这个题思路产生的关键。
下面分类讨论：
在每个询问中 $LCA$ 为在这次询问中所涉及的所有被占据结点的 $LCA$ ， $V$ 为首都位置

$V$ 不是 $LCA$ 的子孙，此时答案为 $V$ 到 $LCA$ 的距离
$V$ 是 $LCA$ 的子孙。

对于第二种有必要再一次进行分类：

点 $V$ 为被占领的点之一，此时答案为 $0$ 。
点 $V$ 不为被占领的点，且点 $V$ 到 $LCA$ 的路径上存在点 $u!=LCA$ 并且 $u$ 被占领，此时答案为V到最近的这样的点u的距离。
点 $V$ 不为被占领的点，且第二类条件种描述的点不存在，此时答案为 $LCA$ 到 $V$ 的距离。

用图来表示（黑色表示被占领，白色表示没有被占领）：

第一类：

第二类：

第三类：

这三种情况的答案都可以用V到V在DFS序中左边最近的点或右边最近的点的LCA的距离来描述。（这一点我觉得不是很好想到。不知道是不是一种套路）用二分来查找
实现的一些细节或用到的知识：

求LCA的算法
LCA的一些基本性质
$u,v$ 两点的距离用 $两点的深度和-2*LCA(u,v)$ 来求
求DFS序以及DFS序的一些特点
二分

总体时间复杂度 $O(Slog(S))$ (S为所有帮派占据的据点数目之和)

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=1e6+20;
const int DEG=20;
const int INF=0x3f3f3f3f;
const LL MOD=1e9+7;
int T;
int N;
//链式前向星村边
int head[MAX_N],tot;
struct Edge{
    int to,nxt;
}edge[MAX_N*2];
void addedge(int u,int v){
    edge[tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}
void init(){
    tot=0;
    memset(head,-1,sizeof(head));
}

//求LCA
int fa[MAX_N][DEG];
int deg[MAX_N];
void BFS(int root){
    queue<int>que;
    deg[root]=0;
    fa[root][0]=root;
    que.push(root);
    while(!que.empty()){
        int tmp=que.front();
        que.pop();
        for(int i=1;i<DEG;i++){
            fa[tmp][i]=fa[fa[tmp][i-1]][i-1];
        }
        for(int i=head[tmp];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==fa[tmp][0])continue;
            deg[v]=deg[tmp]+1;
            fa[v][0]=tmp;
            que.push(v);
        }
    }
}
int LCA(int u,int v){
    if(deg[u]>deg[v])swap(u,v);
    int hu=deg[u],hv=deg[v];
    int tu=u,tv=v;
    for(int det=hv-hu,i=0;det;det>>=1,i++){
        if(det&1)tv=fa[tv][i];
    }
    if(tu==tv)return tu;
    for(int i=DEG-1;i>=0;i--){
        if(fa[tu][i]==fa[tv][i])continue;
        tu=fa[tu][i];
        tv=fa[tv][i];
    }
    return fa[tu][0];

}
//求DFS序
int dfsn[MAX_N];
int pos[MAX_N];
int dfst=0;
void DFS(int v,int fa){
    dfsn[v]=++dfst;
    pos[dfst]=v;
    for(int i=head[v];i!=-1;i=edge[i].nxt){
        int u=edge[i].to;
        if(u==fa)continue;
        DFS(u,v);
    }
}
int dis(int u,int v){
    int res=deg[u]+deg[v]-2*deg[LCA(u,v)];
    return res;
}
//lc存每一个帮派的LCA
//g存每一个帮派的DFS序
int lc[MAX_N];
vector<int> g[MAX_N];
int n;
int u,v;
void input(){
    init();
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    BFS(1);
    DFS(1,-1);
    int k;
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        int c,x;
        scanf("%d",&c);
        for(int j=1;j<=c;j++){
            scanf("%d",&x);
            if(j==1)lc[i]=x;
            else lc[i]=LCA(lc[i],x);
            g[i].push_back(dfsn[x]);
        }
        sort(g[i].begin(),g[i].end());
        //cout<<lc[i]<<endl;
    }
    //cout<<"****"<<endl;
}
int t[MAX_N];
void solve(){
    int q,u,cnt;

    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&u,&cnt);
        for(int i=1;i<=cnt;i++){
            scanf("%d",&t[i]);
        }
        int lca=lc[t[1]];
        for(int i=2;i<=cnt;i++)lca=LCA(lca,lc[t[i]]);

        if(LCA(lca,u)!=lca){
            printf("%d\n",dis(lca,u));

            continue;
        }
        int ans=INF;
        for(int i=1;i<=cnt;i++){
            int tmp=t[i];
            auto p=lower_bound(g[tmp].begin(),g[tmp].end(),dfsn[u]);
            if(p!=g[tmp].end()){
                ans=min(ans,dis(u,LCA(u,pos[*p])));
            }
            if(p!=g[tmp].begin()){
                ans=min(ans,dis(u,LCA(u,pos[*prev(p)])));
            }
        }
        printf("%d\n",ans);
    }
}
int main(){

    //ios::sync_with_stdio(false);
    //cin.tie(0),cout.tie(0);
    //freopen("1.in","r",stdin);
    input();
    solve();

}

好难啊，

这篇文章参考了下面几篇大佬的题解：
https://blog.nowcoder.net/n/9448f4842df840aaae7d09d498d93a30
https://blog.nowcoder.net/n/d3efe1ab597b4d09a6926c42093f9e4f
https://ac.nowcoder.com/discuss/447935