# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3772 |

3 | tourist | 3706 |

4 | maroonrk | 3609 |

5 | Um_nik | 3591 |

6 | fantasy | 3526 |

7 | ko_osaga | 3500 |

8 | inaFSTream | 3477 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 185 |

2 | awoo | 182 |

3 | nor | 172 |

4 | -is-this-fft- | 170 |

5 | adamant | 169 |

6 | maroonrk | 165 |

7 | antontrygubO_o | 160 |

8 | SecondThread | 159 |

9 | dario2994 | 152 |

9 | kostka | 152 |

Give you an undirected graph with no guarantee of connectivity, Erase 2 edges to minimize the maximum connected block. You only need to output The size of the largest connected block.

How to solve it in less than O(N^2) Time Complexity ?

Sorry of my suck English :(

**UPD:** We have found an another O(N^2) Algorithm. We can check all edges, try to delete the edges that we are checking, and then use the Tarjan's algorithm (Tarjan, R. E. (1974). "A note on finding the bridges of a graph") for the remaining edges. Perhaps optimizing this algorithm can reduces time complexity.

Just like title, Is it better to open the memory pool or a vector to save a graph?

I personally like using **Vector** to save a graph...

I just learned graph theory, so I don't know how to use it. :(

memory pool:

```
struct Edge{
int next;
int to;
int w;
};
void add(int u,int v,int w) {
edge[cnt].w = w;
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
```

As everyone knows, my friend Billy2007 is not good at The algorithm of tree, So I and he write this blog.

LCA , that is, the recent Common ancestor, refers to the root tree, find out one or two nodes u and v recent Common ancestor.

For example:

Given a tree with multiple branches, the public ancestor that is closest to the specified two points is requested.

Input: The first line contains three positive integers, $$$N,M,S$$$ which respectively represent the number of nodes in the tree, the number of inquiries, and the number of root nodes. Next, $$$n-1$$$ rows each contain two positive integers $$$x, y$$$ indicating that there is a directly connected edge between $$$x$$$ node and $$$y$$$ node (the data is guaranteed to form a tree). Next, $$$M$$$ rows each contain two positive integers $$$a$$$,$$$b$$$, which means that the nearest common ancestor of $$$a$$$ and $$$b$$$ is inquired.

Output: The output contains $$$M$$$ rows, each containing a positive integer, which in turn is the result of each query.

Guys,how to solve it?

**2.1.Brute force(XD)**

Let the two points search like *merge-find set* :

```
struct node{
int bianh;
int fa,chd[N/1000];
node(){
fa=0;
bianh=0;
memset(chd,0,sizeof(chd));
}
};
int lca(int a,int b){
if(a==b) return a;
return lca(nd[a].fa,nd[b].fa);
}
```

But there is some problem with this algorithm.

Obviously we don't know if $$$a$$$ is the father of $$$b$$$ or $$$b$$$ is the father of $$$a$$$.

This problem can be solved by depth-first search.

But, This algorithm will waste lots of Meomry.

And even if it were possible, the DFS time complexity is $$$O(n)$$$, every time the worst time complexity is $$$O(n)$$$, the total time complexity is $$$O(nm)$$$, will definitely TLE.

**2.2.Multiplication algorithm**

We can use the multiplication algorithm -- an algorithm that achieves $$$O(\log n)$$$ to ask the LCA by recording the first $$$2^i$$$ generation of $$$a$$$.

**Will update after 6 hours.**

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2023 14:27:45 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|