舞钢市住房和城乡建设局网站,如何做视频网站的广告推广,着陆页制作网站,wordpress报名系统传送门:牛客
题目描述:
题目较长,此处省略
输入:
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有以下几种情况:
当vvv不是我们LCALCALCA的子节点.因为我们的被占领的地方肯定是一个联通图,所以此时我们的最短距离显然是vvv到第一个联通图上的一点,那么此时的那一个点就是我们的LCA(可以自己画图理解理解)我们的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]−2∗dist[LCA(u,v)]
下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int fa[maxn],Size[maxn],max_son[maxn],dep[maxn];
vectorintedge[maxn];
void dfs1(int u,int per_u) {Size[u]1;for(int i0;iedge[u].size();i) {int vedge[u][i];if(vper_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 i0;iedge[u].size();i) {int vedge[u][i];if(vfa[u]||vmax_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);ufa[top[u]];}if(dep[u]dep[v]) swap(u,v);return u;
}/**/int n,k;int c[maxn],lc[maxn],t[maxn];//lc记录每一个帮派管的点的LCA
vectorintg[maxn];//记录每一个帮派管的点的dfs序
int dfsn[maxn],dfscnt0,pos[maxn];//记录dfs序
void dfs(int u,int per_u) {dfsn[u]dfscnt;pos[dfscnt]u;for(int i0;iedge[u].size();i) {int vedge[u][i];if(vper_u) continue;dfs(v,u);}
}
int get_dist(int u,int v) {return dep[u]dep[v]-2*dep[LCA(u,v)];
}/**/int main() {nread();for(int i1;in-1;i) {int uread(),vread();edge[u].push_back(v);edge[v].push_back(u);}dfs1(1,0);dfs2(1,1);dfs(1,1);int kread();for(int i1;ik;i) {int numread();for(int j1;jnum;j) {c[j]read();if(j1) 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 qread();for(int i1;iq;i) {int vread(),numread();for(int j1;jnum;j) t[j]read();int lcalc[t[1]];for(int j2;jnum;j) lcaLCA(lca,lc[t[j]]);if(LCA(lca,v)!lca) {printf(%d\n,get_dist(lca,v));continue;}int ansint_INF;for(int j1;jnum;j) {int tmpt[j];auto plower_bound(g[tmp].begin(),g[tmp].end(),dfsn[v]);if(p!g[tmp].end()) { ansmin(ans,get_dist(v,LCA(v,pos[*p])));}if(p!g[tmp].begin()) {ansmin(ans,get_dist(v,LCA(v,pos[*prev(p)])));}}coutansendl;}return 0;
}
