### Inversentropir-36's blog

By Inversentropir-36, history, 2 years ago,

Just like this, I don't know what happend.

Of course I didn't compete in 1970 XD

• +16

By Inversentropir-36, history, 2 years ago,

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.

• +13

By Inversentropir-36, history, 3 years ago,

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;
}


• +8

By Inversentropir-36, history, 3 years ago,

#### 1.introduction

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.

• -4