一诺千金 网站建设,cps广告联盟,哈尔滨网页设计学校,h5手机制作软件app有哪些来源#xff1a;牛客网 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 5秒#xff0c;其他语言10秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 树国是一个有n个城市的国家#xff0c;城市编号…来源牛客网
文章目录题目描述题解代码时间限制C/C 5秒其他语言10秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 树国是一个有n个城市的国家城市编号为1∼n。连接这些城市的道路网络形如一棵树 即任意两个城市之间有恰好一条路径。城市中有k个帮派编号为1∼k。每个帮派会占据一些城市以进行非法交易。有时帮派之间会结盟这就使得城市更加不安全了。同一座城市中可能有多个帮派。 当一些帮派结成联盟时他们会更加强大同时也更加危险。他们所控制的城市数会显著增加。具体地一个联盟控制的城市是联盟中所有帮派所占据的城市再加上这些城市两两之间路径上的所有城市。 shy是树国的市长他想要选择一个城市作为首都。在决定之前他要先做一些调研。为此他找来你帮他回答一些询问你能做到吗在每个询问中shy会选择一个城市作为首都同时会告诉你当前活跃的帮派的集合。在这个询问中你只需要考虑给定的集合中的帮派其他的帮派你可以当作不存在。已知给定集合中的这些帮派结成了联盟shy希望抓获联盟中的人以得到关于整个联盟的一些信息。为此他要找到被联盟控制的所有城市中离首都最近的一座城市到首都的距离。有可能首都本身就被控制了此时答案为0。请注意询问之间相互独立互不影响。 输入描述: 输入的第一行包含一个整数n代表树国中的城市数。 接下来n−1行每行包含两个整数u和v代表城市u和v之间存在一条道路。 接下来一行包含一个整数k代表树国中的帮派数。 接下来k行每行描述一个帮派。第i行的第一个整数c[i]代表第i个帮派占据的城市数接下来c[i]个整数代表被第i个帮派占据的城市。 接下来一行包含一个整数Q代表询问数。 接下来Q行每行描述一个询问。每行的前两个整数V和t[i]代表本次询问中的首都与需要考虑的帮派集合的大小。接下来t[i]个整数代表本次询问中需要考虑的帮派。. 输出描述: 对于每个询问输出一行包含一个整数代表询问的答案。 示例1 输入
7
1 2
1 3
2 4
2 5
3 6
3 7
2
2 6 7
1 4
3
5 1 2
1 1 1
5 2 1 2输出
2
1
1备注: 对于30%的数据1≤n,k,Q≤1000, 1≤每个帮派占据城市数之和≤1000, 1≤每个询问中考虑的帮派数之和≤1000 对于60%的数据1≤n,k,Q≤100000, 1≤每个帮派占据城市数之和≤100000, 1≤每个询问中考虑的帮派数之和≤100000 对于100%的数据1≤n,k,Q≤500000, 1≤每个帮派占据城市数之和≤500000, 1≤每个询问中考虑的帮派数之和≤500000 题解
第一反应lca最近好多lca的题 题目本质就是求一个点即题目中的首都到lcax,y上的点即被控制的城市的最短路径 被控制的城市其实就形成了一个子树 分情况讨论 1.城市不在被控制的子树里面如图 紫色是城市橙色是被控制子树那距离就是首都到子树的距离 sumdep[首都]dep[lca(城市x)]-dep[lca(城市x首都)] 城市x就是lcax,y的值(x和y就是题目所给的帮派) 2.首都被控制 首都被控制分为直接控制帮派点为首都 或间接控制首都在帮派之间的线路上 那距离就是0 3.首都没被控制但是首都在被控制的子树中 首都的前驱被控制后继没被控制 对于这种情况我们就要找首都的的前驱后继点这样好判断距离 可以用dfs序因为dfs序就保存着各个点的顺序 然后可以用二分来降低复杂度 如果首都到LCA的路径上存在一个点xx被占领xlca那么答案就是首都到最近一个符合这个条件的点 lca详细讲解 dfs序详细讲解 为什么这些知识点我都会但是我就不会做题。。哭o(╥﹏╥)o
代码
写完再加上。。。最近有点懒 好吧我放弃了写完一直改一直wa难受自闭了 借鉴的大佬的代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int MAX_N1e620;
const int DEG20;
const int INF0x3f3f3f3f;
const LL MOD1e97;
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].tov;edge[tot].nxthead[u];head[u]tot;
}
void init(){tot0;memset(head,-1,sizeof(head));
}//求LCA
int fa[MAX_N][DEG];
int deg[MAX_N];
void BFS(int root){queueintque;deg[root]0;fa[root][0]root;que.push(root);while(!que.empty()){int tmpque.front();que.pop();for(int i1;iDEG;i){fa[tmp][i]fa[fa[tmp][i-1]][i-1];}for(int ihead[tmp];i!-1;iedge[i].nxt){int vedge[i].to;if(vfa[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 hudeg[u],hvdeg[v];int tuu,tvv;for(int dethv-hu,i0;det;det1,i){if(det1)tvfa[tv][i];}if(tutv)return tu;for(int iDEG-1;i0;i--){if(fa[tu][i]fa[tv][i])continue;tufa[tu][i];tvfa[tv][i];}return fa[tu][0];}
//求DFS序
int dfsn[MAX_N];
int pos[MAX_N];
int dfst0;
void DFS(int v,int fa){dfsn[v]dfst;pos[dfst]v;for(int ihead[v];i!-1;iedge[i].nxt){int uedge[i].to;if(ufa)continue;DFS(u,v);}
}
int dis(int u,int v){int resdeg[u]deg[v]-2*deg[LCA(u,v)];return res;
}
//lc存每一个帮派的LCA
//g存每一个帮派的DFS序
int lc[MAX_N];
vectorint g[MAX_N];
int n;
int u,v;
void input(){}
int t[MAX_N];
int main(){init();scanf(%d,n);for(int i1;in;i){scanf(%d%d,u,v);addedge(u,v);addedge(v,u);}BFS(1);DFS(1,-1);int k;scanf(%d,k);for(int i1;ik;i){int c,x;scanf(%d,c);for(int j1;jc;j){scanf(%d,x);if(j1)lc[i]x;else lc[i]LCA(lc[i],x);g[i].push_back(dfsn[x]);}sort(g[i].begin(),g[i].end());//coutlc[i]endl;}//cout****endl;int q,u,cnt;scanf(%d,q);while(q--){scanf(%d%d,u,cnt);for(int i1;icnt;i){scanf(%d,t[i]);}int lcalc[t[1]];for(int i2;icnt;i)lcaLCA(lca,lc[t[i]]);if(LCA(lca,u)!lca){printf(%d\n,dis(lca,u));continue;}int ansINF;for(int i1;icnt;i){int tmpt[i];auto plower_bound(g[tmp].begin(),g[tmp].end(),dfsn[u]);if(p!g[tmp].end()){ansmin(ans,dis(u,LCA(u,pos[*p])));}if(p!g[tmp].begin()){ansmin(ans,dis(u,LCA(u,pos[*prev(p)])));}}printf(%d\n,ans);}}
