# 某岛

… : "…アッカリ～ン . .. . " .. .
April 6, 2012

## SGU 507. Treediff

( n <= 50000 )

### Analysis:

… . 启发式合并。。

const int N = 50009;

SI S[N]; queue<int> Q;
int p[N], c[N], h[N], res[N], n, m;

int main(){

//freopen("in.txt", "r", stdin);

RD(n, m); fill(res, res + n, 0x7fffffff); FOR(i, 1, n) ++c[--_RD(p[i])];

REP(i, n) h[i] = i; FOR(i, n - m, n) S[i].insert(RD()), Q.push(i);

while (!Q.empty()){
int u = Q.front(); Q.pop();

#define uu h[u]
#define v p[u]
#define vv h[v]

if (SZ(S[vv]) < SZ(S[uu])) swap(uu, vv);

if (S[vv].empty()){
res[v] = res[u];
vv = uu;
}
else {

checkMin(res[v], res[u]);

/*
SI::iterator jt, kt; pair<SI::iterator, bool> tmp; ECH(it, S[uu]){
tmp = S[vv].insert(*it); if (!tmp.second) {res[v] = 0; break;}
else {
jt = tmp.first;
if (jt != S[vv].begin()) kt = jt, --kt, checkMin(res[v], *jt - *kt);
kt = jt; ++kt; if (kt != S[vv].end()) checkMin(res[v], *kt - *jt);
}
}
*/

SI::iterator jt; ECH(it, S[uu]){
SI::iterator jt = S[vv].lower_bound(*it);
if(jt != S[vv].end()) res[v] = min(res[v], *jt - *it);
if(jt != S[vv].begin()) res[v] = min(res[v], *it - *--jt);
if (!res[v]) break;
}

if (res[v]) ECH(it, S[uu]) S[vv].insert(*it);

}

if (!--c[v] && v) Q.push(v);
}

REP(i, n - m) cout << res[i] << " ";
cout << endl;
}