当前位置: 首页 > news >正文

广西住房与城乡建设厅网站电话seoheuni

广西住房与城乡建设厅网站电话,seoheuni,吉安建设公司网站,假电影网站做注册传送门:牛客 题目描述: 题目较长,此处省略 输入: 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一道比较复杂的树题.需要一些复杂的讨论以及LCA知识 对于LCA,可以使用树链剖分进行解决 然后我们看一下题目,我们会发现有这样一个简单的结论,那就…

传送门:牛客

题目描述:

题目较长,此处省略
输入:
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

一道比较复杂的树题.需要一些复杂的讨论以及LCA知识

对于LCA,可以使用树链剖分进行解决

然后我们看一下题目,我们会发现有这样一个简单的结论,那就是我们的两个点<u,v>被占领的时候,那么他们的祖先LCA(u,v)LCA(u,v)LCA(u,v)也必然是被占领的.(这个很好理解,因为我们的,uv肯定是穿过他们的祖先节点的).所以我们可以预处理出每一个帮派的LCALCALCA

同样的对于我们后来的联盟,我们可以求出这些联盟共同的LCALCALCA

那么对于一个首都vvv来说,此时的vvv有以下几种情况:

  1. vvv不是我们LCALCALCA的子节点.因为我们的被占领的地方肯定是一个联通图,所以此时我们的最短距离显然是vvv到第一个联通图上的一点,那么此时的那一个点就是我们的LCA(可以自己画图理解理解)
  2. 我们的vvv是我们的LCALCALCA的子节点.
    此时我们可以预处理出所有节点的dfsdfsdfs序,那么对于此时我们的vvv来说,又有这几种情况:.
    1.比v dfsdfsdfs序小的最近节点的是v的父亲,此时显然最短距离就是这个点与v的距离,注意肯定是一个联通图,而我们的v处于这个位置,所以在v的节点中不可能存在一个点是被占领的
    2.比v dfsdfsdfs序小的最近节点是vvv的兄弟,设为u1,此时我们需要看一下dfsdfsdfs大的最近节点(设为u2)的情况,根据dfs遍历的性质,dfs序大的节点不可能是v的父亲了,此时必然是v的兄弟.所以此时我们的LCA(u1,v)和LCA(u2,v)的一个点到v的距离必然有一个是最短的.这里感觉很难说明清楚,因为用到了dfs遍历的性质,感觉使用到了dfs遍历中的夹逼性质,但是通过画图还是很好理解的

对于树上两点之间距离,可以使用到根节点的距离来进行解决
dis[u][v]=dist[u]+dist[v]−2∗dist[LCA(u,v)]dis[u][v]=dist[u]+dist[v]-2*dist[LCA(u,v)]dis[u][v]=dist[u]+dist[v]2dist[LCA(u,v)]

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int fa[maxn],Size[maxn],max_son[maxn],dep[maxn];
vector<int>edge[maxn];
void dfs1(int u,int per_u) {Size[u]=1;for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==per_u) continue;dep[v]=dep[u]+1;dfs1(v,u);fa[v]=u;Size[u]+=Size[v];if(Size[v]>Size[max_son[u]]) {max_son[u]=v;}}
}
int top[maxn];
void dfs2(int u,int t) {top[u]=t;if(!max_son[u]) return ;dfs2(max_son[u],t);for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==fa[u]||v==max_son[u]) continue;dfs2(v,v);}
}
int LCA(int u,int v) {while(top[u]!=top[v]) {if(dep[top[u]]<dep[top[v]]) swap(u,v);u=fa[top[u]];}if(dep[u]>dep[v]) swap(u,v);return u;
}/*============================================================*/int n,k;int c[maxn],lc[maxn],t[maxn];//lc记录每一个帮派管的点的LCA
vector<int>g[maxn];//记录每一个帮派管的点的dfs序
int dfsn[maxn],dfscnt=0,pos[maxn];//记录dfs序
void dfs(int u,int per_u) {dfsn[u]=++dfscnt;pos[dfscnt]=u;for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==per_u) continue;dfs(v,u);}
}
int get_dist(int u,int v) {return dep[u]+dep[v]-2*dep[LCA(u,v)];
}/*============================================================*/int main() {n=read();for(int i=1;i<=n-1;i++) {int u=read(),v=read();edge[u].push_back(v);edge[v].push_back(u);}dfs1(1,0);dfs2(1,1);dfs(1,1);int k=read();for(int i=1;i<=k;i++)  {int num=read();for(int j=1;j<=num;j++) {c[j]=read();if(j==1) lc[i]=c[j];else lc[i]=LCA(lc[i],c[j]);g[i].push_back(dfsn[c[j]]);}sort(g[i].begin(),g[i].end());}int q=read();for(int i=1;i<=q;i++) {int v=read(),num=read();for(int j=1;j<=num;j++) t[j]=read();int lca=lc[t[1]];for(int j=2;j<=num;j++) lca=LCA(lca,lc[t[j]]);if(LCA(lca,v)!=lca) {printf("%d\n",get_dist(lca,v));continue;}int ans=int_INF;for(int j=1;j<=num;j++) {int tmp=t[j];auto p=lower_bound(g[tmp].begin(),g[tmp].end(),dfsn[v]);if(p!=g[tmp].end()) {		ans=min(ans,get_dist(v,LCA(v,pos[*p])));}if(p!=g[tmp].begin()) {ans=min(ans,get_dist(v,LCA(v,pos[*prev(p)])));}}cout<<ans<<endl;}return 0;
}
http://www.khdw.cn/news/25723.html

相关文章:

  • 兰州做网站的公司大连seo关键词排名
  • 网站建设轮播大图seo门户 site
  • bootstrap网站开发百度百科官网首页
  • 楚雄做网站免费建站的平台
  • 做网站的公司广州seo网站权重
  • 如何设计一个网页的快捷方式seo网站建设公司
  • 廊坊关键词排名软件枫树seo
  • 做网站测试 怎么兼容ie9重庆最新数据消息
  • cdn 动态网站 加速北京网站推广服务
  • 威海外贸网站建设电话服务营销的概念
  • 商务网站建设与规划百度上海总部
  • 网站建设万首先金手指12cilimao磁力猫
  • 塘厦 网站建设 百度推广优化大师电脑版下载
  • 如何建设网站盈利seo上首页排名
  • 什么网站做弹窗广告好北京计算机培训机构哪个最好
  • 电子商务网站建设实习网络营销成功案例有哪些
  • 做我韩国连续剧网站济南做网站建设的公司
  • h5 服装网站模板广州百度推广排名优化
  • 怎么在网站添加paypal百度业务范围
  • 怎么做淘宝联盟网站制作it培训机构培训费用
  • 如何做网站测试it培训四个月骗局
  • wordpress主题整站杭州产品推广服务公司
  • 鸟人 网站建设推广文章的步骤
  • 网站开发业务流程图国际新闻头条最新消息
  • 有没有做生物科技相关的网站营销方案策划书
  • 娄底网站建设是什么品牌营销策划方案
  • 传统文化网站设计深圳网站优化平台
  • vip解析网站如何做写一篇软文推广自己的学校
  • wordpress是建站工具 还是语言seo排名的职位
  • 成都网站seo设计seo的工作原理