出题人题解 | #旅行#

原题解链接：https://ac.nowcoder.com/discuss/163610

题目大意 给定一棵树和树上的一些点集，多次询问一个点到某个点集的距离的最小值。

题目分析 我们不妨对每个点集建立虚树，那就相当于从虚树上找到离询问点最近的那个点，再加上虚树上这个点到询问点集中的点的距离的最小值。

那么现在的问题就是如何找到虚树里询问点最近的那个点。

首先，如果询问点不在虚树根的这个子树里，那么虚树的根就是我们要找的那个点，否则肯定就是这种情况：

假设$A,BA,B$两点是虚树上的相邻的点，C是我们的询问点。

那么我们要找的点肯定是$A,BA,B$中的一个点。

考虑我们怎么找$AA$点，考虑$AA$点有哪些限制。

$AA$点的$DFSDFS$序小于$CC$点。

A点是第一个子树包含$CC$的点。

那么对于第一个限制，我们可以直接二分来确定A点的大致范围，对于第二个限制，我们可以用线段树维护每个点

子树内所包含点的$DFSDFS$序的最大值，然后线段树维护区间最大值，在线段树上二分就能找到A了。

找到$AA$了以后找$BB$的方法也就很简单了，我们对虚树的每个点开个$mapmap$，若存在虚边$x\to yx\; \backslash rightarrow\; y$，且原树上$xx$到$yy$路径上的第一个点是$zz$，那么我们令$mp[x][z]=ymp[x][z]=y$。然后我们通过倍增找到$A\to CA\; \backslash rightarrow\; C$路径上的第一个点$DD$，然后查$mp[A][D]mp[A][D]$就是$BB$了。

找到点$A,BA,B$后就可以用这两个更新答案了。

注意，我们先在虚树上$DFSDFS$求出每个点到离它最近的点集中的点的距离然后用这个距离加上$CC$到$AA$或$BB$的距离更新答案。

复杂度$\mathcal{O}(n\log n)\backslash mathcal\{O\}(n\; \backslash log\; n)$

当然你可以直接动态点分治，由于数据范围比较小就跑过去了

手写 $hashhash$ 可以踩 $stdstd$

#include "bits/stdc++.h"
using namespace std;
const int N = 1e6 + 10;
int n, m, q;
vector<int> ids[N], g[N];

typedef long long ll;

struct FastIO{
    static const int S=1e7;
    int wpos;
    char wbuf[S];
    FastIO():wpos(0){}

    inline int xchar()
		{
			static char buf[S];
			static int len=0,pos=0;
			if(pos==len)
				pos=0,len=fread(buf,1,S,stdin);
			return buf[pos++];
		}

    inline int operator () ()
		{
			int c=xchar(),x=0,ng=0;
			while (!isdigit(c)) ng|=(c=='-'),c=xchar();
			for(;isdigit(c);c=xchar()) x=x*10+c-'0';
			return ng?-x:x;
		}

    inline ll operator ! ()
		{
			int c=xchar(),ng=0;ll x=0;
			while(!isdigit(c)) ng|=(c=='-'),c=xchar();
			for(;isdigit(c);c=xchar()) x=x*10+c-'0';
			return ng?-x:x;
		}

    inline void wchar(int x)
		{
			if(wpos==S) fwrite(wbuf,1,S,stdout),wpos=0;
			wbuf[wpos++]=x;
		}

    inline void operator () (ll x)
		{
			if (x<0) wchar('-'),x=-x;
			char s[24];
			int n=0;
			while(x||!n) s[n++]='0'+x%10,x/=10;
			while(n--) wchar(s[n]);
			wchar('\n');
		}

    inline void space(ll x)
		{
			if (x<0) wchar('-'),x=-x;
			char s[24];
			int n=0;
			while(x||!n) s[n++]='0'+x%10,x/=10;
			while(n--) wchar(s[n]);
			wchar(' ');
		}

    inline void nextline() {wchar('\n');}

    ~FastIO() {if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;}
}io;

int dep[N], fa[N][22], dfn[N], dfn_end[N], dfn_clk,lstans;
void dfs_lca(int u, int fa) {
    dfn[u] = ++ dfn_clk;
    dep[u] = dep[fa] + 1;
    :: fa[u][0] = fa;
    for(int i = 1 ; i <= 20 ; ++ i) {
        :: fa[u][i] = :: fa[:: fa[u][i - 1]][i - 1];
    }
    for(int v: g[u]) {
        if(v != fa) {
            dfs_lca(v, u);
        }
    }
    dfn_end[u] = dfn_clk;
}
int getlca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 20 ; ~ i ; -- i) {
        if(dep[fa[u][i]] >= dep[v]) {
            u = fa[u][i];
        }
    }
    if(u == v) return u;
    for(int i = 20 ; ~ i ; -- i) {
        if(fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int f[N] = { 0x3f3f3f3f }, root, sz[N], siz, ban[N];

void getrt(int u, int fa) {
    f[u] = 0, sz[u] = 1;
    for(int v: g[u]) {
        if(v != fa && !ban[v]) {
            getrt(v, u);
            sz[u] += sz[v];
            f[u] = max(f[u], sz[v]);
        }
    }
    f[u] = max(f[u], siz - sz[u]);
    if(f[u] < f[root]) root = u;
}

unordered_map<int, int> h[N];

void dfs(int u, int fa, int neko, int dis) {
    for(int col: ids[u]) {
        if(h[neko].count(col)) {
            h[neko][col] = min(h[neko][col], dis);
        } else {
            h[neko][col] = dis;
        }
    }
    for(int v: g[u]) {
        if(v != fa && !ban[v]) {
            dfs(v, u, neko, dis + 1);
        }
    }
}

int top[N];

void sol(int u) {
    // printf("sol %d\n", u);
    ban[u] = 1;
    dfs(u, 0, u, 0);
    for(int v: g[u]) {
        if(!ban[v]) {
            root = 0, siz = sz[v], getrt(v, 0), top[root] = u, sol(root);
        }
    }
}

int getdis(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[getlca(u, v)];
}

int main() {
	int t=clock();
	n=io();m=io();q=io();
    for(int i = 1, u, v ; i < n ; ++ i) {
		u=io();v=io();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs_lca(1, 0);
    for(int i = 1 ; i <= m ; ++ i) {
		int cnt = io();
        for(int j = 1 ; j <= cnt ; ++ j) {
            ids[io()].push_back(i);
        }
    }
    root = 0, siz = n, getrt(1, 0), sol(root);
    while(q --) {
		int u, neko; u=(io()+lstans)%n+1;neko=(io()+lstans)%m+1;
       int ans = n, nya = u;
       for( ; u ; u = top[u]) {
           if(h[u].count(neko)) {
               ans = min(ans, getdis(nya, u) + h[u][neko]);
           }
       }
       io(lstans=ans);
    }
}