某岛

… : "…アッカリ～ン . .. . " .. .

April 6, 2012

SGU 507. Treediff

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

External link:

http://acm.sgu.ru/problem.php?contest=0&problem=507

Posted by xiaodao
Category: SGU

某岛

SGU 507. Treediff

Brief description:

Analysis:

External link:

Archives

Blogroll

Links

Myself

Project