网站建设会议记录,wordpress 免费企业主题,开发游戏的职业叫什么,网站建设人力资源分配世界树
金牌导航 虚树-1
luogu 3233
题目大意
对于一棵树#xff0c;给出若干询问#xff0c;每个询问告诉你若干个特殊点#xff0c;对于所有点#xff0c;都会选择离自己最近#xff08;距离相等就选编号最小的#xff09;的特殊点#xff0c;问对于所有特殊点给出若干询问每个询问告诉你若干个特殊点对于所有点都会选择离自己最近距离相等就选编号最小的的特殊点问对于所有特殊点有多少个点选择该点
输入样例
10
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
5
2
6 1
5
2 7 3 6 9
1
8
4
8 7 10 3
5
2 9 3 5 8输出样例
1 9
3 1 4 1 1
10
1 1 3 5
4 1 3 1 1数据范围
1⩽n,q,∑i1qmi⩽3×1051\leqslant n,q,\sum_{i1}^q m_i\leqslant 3\times 10^51⩽n,q,∑i1qmi⩽3×105
解题思路
对于每次询问建出相对的虚树 然后DP出虚树中每个点的离特殊点的最短距离 然后计算出分界点得出每个特殊点会被多少点选择这里只讲大概思路详情见代码
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 300100
#define INF 1e8
using namespace std;
int n, m, w, x, y, nn, num, tot, top, s[N], d[N], ss[N], faa[N], dep[N], val[N], ans[N], dfn[N], size[N], head[N], fa[N][30];
struct rec
{int to, next;
}a[N1];
struct node
{int s, v;
}f[N];
bool cmp(int a, int b)
{return dfn[a] dfn[b];
}
void add(int x, int y)
{a[tot].to y;a[tot].next head[x];head[x] tot;
}
void dfs(int x)
{dfn[x] w;//算dfs序size[x] 1;for (int j 1; j 18; j)fa[x][j] fa[fa[x][j - 1]][j - 1];for (int i head[x]; i; i a[i].next)if (a[i].to ! fa[x][0]){fa[a[i].to][0] x;dep[a[i].to] dep[x] 1;dfs(a[i].to);size[x] size[a[i].to];}
}
int lca(int x, int y)
{if (dep[x] dep[y]) swap(x, y);for (int i 18; i 0; --i)if (dep[fa[x][i]] dep[y]) x fa[x][i];for (int i 18; i 0; --i)while(fa[x][i] ! fa[y][i]) x fa[x][i], y fa[y][i];if (x ! y){x fa[x][0];y fa[y][0];}return x;
}
void build()//建虚树
{top 0;d[0] 0;sort(s 1, s 1 nn, cmp);num nn;for (int i 1; i nn; i){int u s[i];if (!top){faa[u] 0;d[top] u;}else{int g lca(d[top], u);while(dep[d[top]] dep[g]){if (dep[d[top - 1]] dep[g])faa[d[top]] g;top--; }if (d[top] ! g){faa[g] d[top];f[g] (node){INF, 0};d[top] g;s[num] g;}faa[u] g;d[top] u;}}sort(s 1, s 1 num, cmp);
}
int jump(int x, int y)//找第y辈祖先
{for (int i 0; i 18; i, y 1)if (y 1) x fa[x][i];return x;
}
void solve()
{for (int i num; i 1; --i)//自下而上求最短距离{int u s[i], v faa[u];if (f[u].s dep[u] - dep[v] f[v].s || f[u].s dep[u] - dep[v] f[v].s f[u].v f[v].v)f[v] (node){f[u].s dep[u] - dep[v], f[u].v};}for (int i 2; i num; i)//自上而下这样就求出了虚树上所有点到特殊点的最短路径{int u s[i], v faa[u];if (f[v].s dep[u] - dep[v] f[u].s || f[v].s dep[u] - dep[v] f[u].s f[v].v f[u].v)f[u] (node){f[v].s dep[u] - dep[v], f[v].v};}for (int i 1; i num; i){int u s[i], v faa[u];val[u] size[u];//子树中所有点都到该点如果有更优解那么再减if (i 1){ans[f[u].v] n - size[u];//dfs序最小的点上方所有点都到这个点因为上方无关键点所以是一条链不存在其他子树continue;}int son jump(u, dep[u] - dep[v] - 1);//找到v的子树中u所在子树的根节点int S size[son] - size[u];//求出之间的节点数val[v] - size[son];//这一部分点暂时不选v如果选那再加if (f[u].v f[v].v) ans[f[u].v] S; //相等那之间的点选择一样else{int g f[u].s - f[v].s dep[u] dep[v] 1 1;//使分界点到两边的特殊点的长度一样if (f[v].v f[u].v f[u].s dep[u] - g f[v].s - dep[v] g) g;//如果两边长度一样选dfs序小的注意这里如果分界点往u移动那么到u的点-1到v的点1g size[jump(u, dep[u] - g)] - size[u];//求出到u的点个数ans[f[u].v] g;ans[f[v].v] S - g; }}for (int i 1; i num; i)ans[f[s[i]].v] val[s[i]];
}
int main()
{scanf(%d, n);for (int i 1; i n; i){scanf(%d%d, x, y);add(x, y);add(y, x);}dep[1] 1;dfs(1);scanf(%d, m);while(m--){scanf(%d, nn);for (int i 1; i nn; i){scanf(%d, s[i]);ss[i] s[i];f[s[i]] (node){0, s[i]};}memset(ans, 0, sizeof(ans));memset(val, 0, sizeof(val));build();solve();for (int i 1; i nn; i)printf(%d , ans[ss[i]]);putchar(10);}return 0;
}
