#include <iostream>
#include <utility>
#include <map>
#include <algorithm>
#include <vector>
#define MAXN 200005
#define fi first
#define se second
using namespace std;
int N, K, P[MAXN], Route[MAXN][2], Ans, pt = 1;
int Preorder[MAXN], Pos[MAXN][2], depth[MAXN], anc[MAXN][19];
vector <pair<int,int> > Path[MAXN];
vector <int> adj[MAXN], Back[MAXN];
//precalc
void preorder(int u) {
Preorder[pt] = u;
Pos[u][0] = pt;
depth[u] = depth[P[u]] + 1;
pt++;
for (int v: adj[u]) {
preorder(v);
}
Pos[u][1] = pt-1;
}
void makejump() {
for (int i=1; i <= N; i++) {
anc[i][0] = P[i];
}
for (int j=1; j<= 18; j++) {
for (int i=1; i <= N; i++) {
anc[i][j] = anc[anc[i][j-1]][j-1];
}
}
}
int lca(int a, int b) {
if (depth[a] > depth[b]) {swap(a,b);}
for (int i=18; i>=0; i--) {
if ((depth[b] - depth[a]) & (1<<i)) {b = anc[b][i];}
}
for (int i=18; i>=0; i--) {
if (anc[a][i] != anc[b][i]) {
a = anc[a][i];
b = anc[b][i];
}
}
if (a != b) {return(anc[a][0]);}
return(a);
}
int D(int a, int b) { //distance
return(depth[a] + depth[b] - 2*depth[lca(a,b)]);
}
void precalc() {
for (int i=2; i<=N; i++) {
adj[P[i]].push_back(i);
}
preorder(1);
makejump();
for (int i=1; i<=K; i++) {
int v = lca(Route[i][0], Route[i][1]);
Back[Route[i][0]].push_back(v);
Back[Route[i][1]].push_back(v);
if (Route[i][0] == v || Route[i][1] == v) {continue;}
Path[v].push_back({Route[i][0], Route[i][1]});
}
}
//classes
class CompressedTree {
int Par[MAXN * 10], big[MAXN * 10], Val[MAXN * 10], len[MAXN * 10], dist[MAXN * 10], V=1;
map<int,int> M[MAXN * 10];
vector <int> Tadj[MAXN * 10];
public:
int addnode(int val, int d) { //root go to 0
Val[V] = val, len[V] = d;
big[V] = V;
V+=1;
return(V-1); //return label assigned to
}
void setpar(int chdId, int parId) {
Par[chdId] = parId;
}
void reset() { //probs can zero other stuff too
for (int i=1; i<V; i++) {
M[i].clear();
Tadj[i].clear();
}
V = 1;
}
void build() {
for (int i=V-1; i>1; i--) {
Tadj[Par[i]].push_back(i);
}
for (int i=2; i<V; i++) {
dist[i] = dist[Par[i]] + len[i];
}
}
int slv(int u, int rt) {
M[u][Pos[Val[u]][0]] = Val[u]; //actual node id of the other one
for (int v: Tadj[u]) {
int res = slv(v, rt);
if (M[res].size() > M[big[u]].size()) {
swap(res, big[u]);
}
for (auto p: M[res]) {
auto it = M[big[u]].upper_bound(p.fi);
if (it != M[big[u]].end()) {
Ans = max(Ans, dist[u] + depth[lca(p.se, (*it).se)] - depth[rt]);
}
if (it != M[big[u]].begin()) {
Ans = max(Ans, dist[u] + depth[lca(p.se, (*(--it)).se)] - depth[rt]);
}
M[big[u]][p.fi] = p.se;
}
}
return(big[u]);
}
} CT;
//solve stuff
int dfs1(int u) { //case where paths don't share lca
int bh = 1 << 30, sbh = 1 << 30;
for (int v: Back[u]) {
if (depth[v] < bh) {
sbh = bh;
bh = depth[v];
} else if (depth[v] < sbh) {
sbh = depth[v];
}
}
for (int v: adj[u]) {
int res = dfs1(v);
if (res < bh) {
sbh = bh;
bh = res;
} else if (res < sbh) {
sbh = res;
}
}
Ans = max(Ans, depth[u] - sbh);
return(bh);
}
void slvLCA(int v) { //slv all path with common lca V
if (Path[v].size() < 2) {return;}
vector <pair<int,int> > Nodes, Nodes2; //fi Nodes is ET, fi Nodes2 is depth
map <int,int> Sweep; //Euler tour, compressed tree Id
for (auto p: Path[v]) {
Nodes.push_back({Pos[p.first][0], p.first});
Nodes.push_back({Pos[p.second][0], p.second});
}
sort(Nodes.begin(), Nodes.end()); //sort by ET
for (int i=0; i<Nodes.size()-1; i++) {
int junction = lca(Nodes[i].second, Nodes[i+1].second);
Nodes2.push_back({depth[junction], junction});
Nodes2.push_back({depth[Nodes[i].second], Nodes[i].second});
Nodes2.push_back({depth[Nodes[i+1].second], Nodes[i+1].second});
}
for (int i=Nodes2.size()-1; i>=0; i--) {
if (i+1 < Nodes2.size() && Nodes2[i] == Nodes[i+1]) {continue;} //remove duplicates
int v = Nodes2[i].second;
int vid = CT.addnode(v, depth[v]);
auto it = Sweep.lower_bound(Pos[v][0]);
for (; it != Sweep.end(); it=Sweep.erase(it)) {
if ((*it).first <= Pos[v][1]) {
CT.setpar((*it).second, vid);
}
}
}
CT.build();
CT.slv(1, v);
CT.reset();
}
int main() {
//freopen("courin.txt","r",stdin);
scanf("%d %d",&N,&K);
for (int i=2; i<=N; i++) {
scanf("%d",&P[i]);
}
for (int i=1; i<=K; i++) {
scanf("%d %d",&Route[i][0], &Route[i][1]);
}
precalc();
dfs1(1);
for (int i=1; i<=N; i++) {
slvLCA(i);
}
printf("%d", Ans);
}
Compilation message
sending.cpp: In function 'void slvLCA(int)':
sending.cpp:160:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for (int i=0; i<Nodes.size()-1; i++) {
| ~^~~~~~~~~~~~~~~
sending.cpp:167:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | if (i+1 < Nodes2.size() && Nodes2[i] == Nodes[i+1]) {continue;} //remove duplicates
| ~~~~^~~~~~~~~~~~~~~
sending.cpp: In function 'int main()':
sending.cpp:184:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
184 | scanf("%d %d",&N,&K);
| ~~~~~^~~~~~~~~~~~~~~
sending.cpp:186:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
186 | scanf("%d",&P[i]);
| ~~~~~^~~~~~~~~~~~
sending.cpp:189:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
189 | scanf("%d %d",&Route[i][0], &Route[i][1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
155212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
155212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
155212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
155212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
480 ms |
344224 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
169276 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
155212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
155212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
