Brief description:
给定一棵 n 个结点的树，叶节点有一个权值，问以每个内结点为根的子树，所有叶节点之间权值差最小的值。
( 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;
}
