Pre knowledge
- You need to know how to find the bridge, otherwise please move P1656 bombing Railway Tarjan approach.
- You need to know the basic properties of edge biconnected components.
thinking
Tip: in the description of "point weight sum of \ (u\to v \) path", the point weight sum includes the point weight of \ (u,v \).
When the Martian cat walks a road, it can't go any further
From this sentence, we can think that if the road is a bridge, the Martian cat will never walk back.
Then we can find the side double union point first. If you can't ask for double sides, you can see This cloud clipboard.
While seeking the edge pair, we can mark whether there is an edge with puffs in the edge pair.
After finding the edge double contraction points, we can build the graph. From the properties of the contraction points of the edge double connected components, we know that the contraction must be a tree, and the edges on the tree are bridges. So the question turns to:
Each point on a tree has a point weight (point weight is whether there are puffs in the two sides of the tree), and each edge has an edge weight (edge weight is whether there are puffs on the bridge). Ask whether the sum of point weight or edge weight on a path of \ (u\to v \) on the tree is greater than or equal to \ (1 \).
We can prefix and from the root down. Each point has two values to store: one is the point weight sum of the path from the root to this point, and the other is the edge weight sum of the path from the root to here.
We then find the LCA of \ ((u,v) \). If you can't LCA, please move on P3379 nearest public ancestor.
Next, for the sum of point weight and edge weight of \ (u\to v \) path, the formula is deduced respectively:
Finally, you only need to check the values of edge weight and point weight.
code
You need to know what my macro definitions mean. You can here View my default source.
The bridge seeking part is omitted here. You can move step by step P1656 bombing Railway The Tarjan practice of learning how to find a bridge.
3.1 finding edge biconnected components
DFS does not use the bridge edge method to calculate the double edge:
void dfs(int x){
eccnum[x]=tnt;
efor(i,x){
int y=edge[i].toe;
if(eccnum[x]==eccnum[y]){//There may be multiple edges with different weights
if(edge[i].val==1){
has[tnt]=1;
}
ctn;//Avoid infinite recursion
}
if(bridge[i]){//No bridge
ctn;
}
if(edge[i].val==1){//The weight of the edge indicates whether there is a puff
has[tnt]=1;
}
dfs(y);
}
}
\The (has \) array indicates whether there is a puff in the edge pair, \ (tnt \) is the number of the biconnected component of the current edge.
The way to call it in the main function is as follows:
fr1(i,1,n){//There is not necessarily only one double edge in the picture
if(!eccnum[i]){
tnt++;
dfs(i);
}
}
Only in this way can we ensure that each point has a corresponding edge pair.
3.2 tree after edge construction and double shrinkage points
Here we only need to pay attention to the details of the chain forward Star:
fr1(i,2,edgecnt-1){
int x=edge[i^1].toe,y=edge[i].toe;
if(eccnum[x]!=eccnum[y]){
p[eccnum[x]].pb(mp(eccnum[y],edge[i].val));
}
}
My chained forward star function is also attached to facilitate understanding of the above code:
int edgecnt=2;
struct Edge{
int toe,val,nex;
} edge[N+N];
int head[N+N];
void add(int x,int y,int w){
edge[edgecnt].toe=y;
edge[edgecnt].val=w;
edge[edgecnt].nex=head[x];
head[x]=edgecnt;
edgecnt++;
}
3.3 initialize LCA and prefix
From here on, we default \ (1 \) to the root of the tree and change the tree into a rooted tree.
Note that pointvalue[1]=has[1] before prefix and point weight, that is, initialize the point weight prefix and at the tree root to whether there are puffs on both sides of the tree root.
Next, you can start DFS from the root of the tree and make edge weight prefix and point weight prefix at the same time. In addition, we can complete the initialization of LCA by the way.
void dfs2(int x,int fa){
deep[x]=deep[fa]+1;
f[x][0]=fa;//Initialize several arrays used to calculate LCA at the same time
fv(i,p[x]){
if(p[x][i].fi!=fa){//Avoid infinite recursion
tsum[p[x][i].fi]=tsum[x]+p[x][i].se;
psum[p[x][i].fi]=psum[x]+has[p[x][i].fi];//Base two prefixes and
dfs2(p[x][i].fi,x);
}
}
}
\(psum \) is the point weight prefix and, \ (tsum \) is the edge weight prefix and. The main function should be called as follows:
psum[1]=has[1];//Non missing initialization!!! dfs2(1,1);
3.4 LCA
Multiply the part of LCA, you can move P3379 nearest public ancestor.
Pay attention to the recursive part of LCA and don't write the loop backwards. As long as you keep in mind the meaning of the \ (f \) array, there will never be a problem.
A reference is given below:
num=log2(n);
fr1(j,1,num){
fr1(i,1,n){
f[i][j]=f[f[i][j-1]][j-1];
}
}
No reference code is given for the part of LCA.
3.5 handling inquiries
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
x=eccnum[x];
y=eccnum[y];
int lcaa=lca(x,y);
if((psum[x]+psum[y]-psum[lcaa]-psum[(lcaa==1?0:f[lcaa][0])])||(tsum[x]+tsum[y]-tsum[lcaa]-tsum[lcaa])){
puts("YES");
}
else{
puts("NO");
}
}
Note that the input is not the number of side pairs. We need to convert it ourselves.
After the LCA is obtained, the formula introduced in the idea can be applied. Note that when calculating the point weight contribution, we need to judge whether \ (lcaa \) is \ (1 \). If so, we can't subtract psum[f[lcaa][0]] (because we use f[1][0]=1) in LCA preprocessing), but subtract \ (0 \).