#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
vector<int> adj[100100], H[100100];
struct Seg{
pair<int, int> tree[400400], lazy[400400];
void init(int i, int l, int r){
tree[i] = lazy[i] = {-1, -1};
if (l==r) return;
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
}
void propagate(int i, int l, int r){
if (lazy[i].second==-1) return;
tree[i] = {r+lazy[i].first, lazy[i].second};
if (l!=r){
lazy[i<<1] = lazy[i];
lazy[i<<1|1] = lazy[i];
}
lazy[i] = {-1, -1};
}
void update(int i, int l, int r, int s, int e, int c, int x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i] = {c, x};
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, c, x); update(i<<1|1, m+1, r, s, e, c, x);
tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
pair<int, int> query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if (r<s || e<l) return {-1, -1};
if (s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
}
void clear(int i, int l, int r, int p){
tree[i] = lazy[i] = {-1, -1};
if (l==r) return;
if (r<p || p<l) return;
int m = (l+r)>>1;
clear(i<<1, l, m, p); clear(i<<1|1, m+1, r, p);
}
};
struct DSU{
int path[100100], root[100100];
void init(const vector<int> &a){
for (int i=0;i<(int)a.size();i++){
path[i] = i;
root[i] = a[i];
}
}
int find(int s){
if (path[s]==s) return s;
return path[s] = find(path[s]);
}
void merge(int l, int r, int v){
l = path[l], r = path[r];
assert(l!=r);
path[r] = l;
root[l] = v;
}
int calc(int s){return root[find(s)];}
}dsu;
namespace HLD{
Seg tree;
vector<int> G[100100], buf;
int par[100100], dep[100100], sz[100100], top[100100], in[100100], INV[100100], cnt;
void dfs0(int s, int pa){
par[s] = pa;
dep[s] = dep[pa] + 1;
sz[s] = 1;
for (auto &v:adj[s]) if (v!=pa){
G[s].push_back(v);
// printf("%d -> %d\n", s, v);
dfs0(v, s);
sz[s] += sz[v];
}
}
void dfs1(int s){
// printf("dfs %d\n", s);
if (!G[s].empty()) swap(G[s][0], *max_element(G[s].begin(), G[s].end(), [&](int i, int j){return sz[i] < sz[j];}));
in[s] = ++cnt;
INV[cnt] = s;
for (auto &v:G[s]){
if (v==G[s][0]) top[v] = top[s];
else top[v] = v;
dfs1(v);
}
}
void init(){
for (int i=1;i<=n;i++) G[i].clear();
top[1] = 1;
cnt = 0;
dfs0(1, 0);
dfs1(1);
tree.init(1, 1, n);
}
pair<int, int> query(int s, int e){
assert(dep[s] <= dep[e]);
pair<int, int> ret = {-1, -1};
while(top[s]!=top[e]){
ret = max(ret, tree.query(1, 1, n, in[top[e]], in[e]));
e = par[top[e]];
assert(dep[s] <= dep[e]);
}
ret = max(ret, tree.query(1, 1, n, in[s], in[e]));
return ret;
}
void update(int s, int e, int x){
assert(dep[s] <= dep[e]);
while(top[s]!=top[e]){
tree.update(1, 1, n, in[top[e]], in[e], -in[e]+dep[e], x);
e = par[top[e]];
assert(dep[s] <= dep[e]);
}
tree.update(1, 1, n, in[s], in[e], -in[e]+dep[e], x);
}
int LCA(int x, int y){
while(top[x]!=top[y]){
if (dep[top[x]] > dep[top[y]]) swap(x, y);
y = par[top[y]];
// printf("ok %d %d\n", x, y);
}
if (dep[x] > dep[y]) swap(x, y);
return x;
}
int calc(int x, int y){
x = INV[x], y = INV[y];
return dep[LCA(x, y)];
}
void push(int x){buf.push_back(x);}
void compress(){
sort(buf.begin(), buf.end(), [&](int i, int j){return in[i] < in[j];});
buf.erase(unique(buf.begin(), buf.end()), buf.end());
for (auto &x:buf) H[x].clear();
vector<array<int, 4>> E;
for (int i=0;i<(int)buf.size()-1;i++){
int lca = LCA(buf[i], buf[i+1]);
E.push_back({dep[lca], lca, i, i+1});
H[lca].clear();
}
sort(E.begin(), E.end(), greater<array<int, 4>>());
dsu.init(buf);
for (auto &[_, v, l, r]:E){
int x = dsu.calc(l), y = dsu.calc(r);
if (dep[v] < dep[x]) H[v].push_back(x);
if (dep[v] < dep[y]) H[v].push_back(y);
dsu.merge(l, r, v);
buf.push_back(v);
}
}
} // namespace HLD
struct DS{
multimap<array<int, 3>, int> st;
multiset<array<int, 3>> stAns;
void clear(){
st.clear();
stAns.clear();
}
void insert(int ord, int ord2, int x){
auto iter = st.find({ord2, ord, x});
if (iter!=st.end()){
auto piter = (iter!=st.begin())?prev(iter):iter;
auto niter = next(iter);
if (iter!=st.begin())
stAns.erase({piter->second, (piter->first)[2], (iter->first)[2]});
if (niter!=st.end())
stAns.erase({iter->second, (iter->first)[2], (niter->first)[2]});
if (iter!=st.begin() && niter!=st.end())
stAns.insert({piter->second = HLD::calc((piter->first)[0], (niter->first)[0]), (piter->first)[2], (niter->first)[2]});
st.erase(iter);
}
else{
iter = st.insert({array<int, 3>{ord, ord2, x}, 0});
auto piter = (iter!=st.begin())?prev(iter):iter;
auto niter = next(iter);
if (iter!=st.begin() && niter!=st.end())
stAns.erase({piter->second, (piter->first)[2], (niter->first)[2]});
if (iter!=st.begin())
stAns.insert({piter->second = HLD::calc((piter->first)[0], (iter->first)[0]), (piter->first)[2], (iter->first)[2]});
if (niter!=st.end())
stAns.insert({iter->second = HLD::calc((iter->first)[0], (niter->first)[0]), (iter->first)[2], (niter->first)[2]});
}
}
array<int, 3> query(){
if (stAns.empty()) return {-1, -1, -1};
return *stAns.rbegin();
}
}D[100100];
vector<int> solve5(vector<array<int, 3>> &Q){
sort(Q.begin(), Q.end(), [&](array<int, 3> i, array<int, 3> j){return HLD::dep[i[0]] < HLD::dep[j[0]];});
vector<int> ret(3);
ret[0] = 0, ret[1] = 0, ret[2] = 1;
for (auto &[s, e, x]:Q){
auto [d, y] = HLD::query(s, e);
HLD::update(s, e, x);
if (d <= HLD::dep[s]) continue;
if (ret[0] < d - HLD::dep[s]){
ret[0] = d - HLD::dep[s];
ret[1] = x;
ret[2] = y;
}
}
return ret;
}
vector<int> ret6;
void merge(DS &D, DS &E){
if (D.st.size() < E.st.size()) swap(D, E);
for (auto &[A, B]:E.st) D.insert(A[0], A[1], A[2]);
}
void dfs2(int s, int root){
for (auto &v:H[s]){
dfs2(v, root);
merge(D[s], D[v]);
}
if (s!=root){
auto [val, x, y] = D[s].query();
if (val==-1) val = -1e9;
val += HLD::dep[s] - HLD::dep[root] * 2;
if (val > ret6[0]){
ret6[0] = val, ret6[1] = x, ret6[2] = y;
}
}
}
vector<int> solve6(int root, vector<array<int, 3>> &Q){
ret6.clear();
ret6.resize(3);
ret6[0] = 0, ret6[1] = 0, ret6[2] = 1;
HLD::buf.clear();
HLD::push(root);
for (auto &[s, e, x]:Q){
HLD::push(s);
HLD::push(e);
}
HLD::compress();
for (auto &x:HLD::buf) D[x].clear();
for (auto &[s, e, x]:Q){
D[s].insert(HLD::in[e], HLD::in[s], x);
D[e].insert(HLD::in[s], HLD::in[e], x);
}
dfs2(root, root);
return ret6;
}
vector<array<int, 3>> buf2[100100];
std::vector<int> post(std::vector<int> U, std::vector<int> V, std::vector<int> S, std::vector<int> E) {
n = U.size() + 1;
k = S.size();
for (int i=0;i<n-1;i++){
U[i]++, V[i]++;
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
HLD::init();
vector<array<int, 3>> buf1;
for (int i=0;i<k;i++){
S[i]++, E[i]++;
int lca = HLD::LCA(S[i], E[i]);
buf1.push_back({lca, S[i], i});
buf1.push_back({lca, E[i], i});
// printf("ok lca = %d\n", lca);
buf2[lca].push_back({S[i], E[i], i});
}
auto ans1 = solve5(buf1);
// return ans1; // subtask 5
HLD::tree.init(1, 1, n);
for (int i=1;i<=n;i++){
auto ans2 = solve6(i, buf2[i]);
if (ans2[0] > ans1[0]) swap(ans1, ans2);
}
return ans1;
}
Compilation message
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
collect2: error: ld returned 1 exit status
