Brief description:

给定一棵 n 个点的点权树，同时结点分为黑点和白点两类。
要求找到一条长度最大的路径，使得路径上经过的黑点数不超过 k 个。

Analysis:

点分治 + 动态规划）
。。。有待分析。

const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 200000 + 9, M = N * 2;

int a[M], b[M], w[M], prd[M], suc[M]; // edge ..
int dist[N], max_dep[N], dep[N], sz[N], hd[N]; bool isBlack[N]; // vertx ..
int L[N], Ln, F[N], Fn, G[N], Gn; // core ..
int n, n_, m, k, _c, c, ans;

inline void remove(int x){
    if (x == hd[a[x]]) prd[hd[a[x]] = suc[x]] = 0;
    else suc[prd[suc[x]] = prd[x]] = suc[x];
}

#define v b[i]
inline void dfs1(int u, int p){
    
    max_dep[u] = dep[u];
    
    if (!p){
        for(int i=hd[u];i;i=suc[i]){
            remove(i^1), dist[v] = dist[u] + w[i], dep[v] = dep[u] + isBlack[v];
            dfs1(v, u), checkMax(max_dep[u], max_dep[v]), L[Ln++] = v;
        }
    }
    else {
        for(int i=hd[u];i;i=suc[i]) if (v != p){
            dist[v] = dist[u] + w[i], dep[v] = dep[u] + isBlack[v];
            dfs1(v, u), checkMax(max_dep[u], max_dep[v]);
        }
    }

}

inline void dfs2(int u, int p){
    
    if (dep[u] >= Gn) return;
    checkMax(G[dep[u]], dist[u]);
    
    for(int i=hd[u];i;i=suc[i]) if (v != p){
        dfs2(v, u);
    }
}

inline void find_center(int u, int p){
    
    int blc = 0; sz[u] = 1;
    
    for(int i=hd[u];i;i=suc[i]) if (v != p){
        find_center(v, u), sz[u] += sz[v];
        checkMax(blc, sz[v]);
    }
    
    checkMax(blc, n_ - sz[u]);
    if (blc <= _c) _c = blc, c = u;
}

inline bool shller(int a, int b){
    return max_dep[a] < max_dep[b];
}

inline void stat(bool rt){
    
    if (!rt || k){
    
        sort(L, L+Ln, shller); Fn = 1; REP(i, Ln){
            
            Gn = min(max_dep[L[i]] + 1, k + !rt), dfs2(L[i], 0);
            FOR(j, 1, Gn) checkMax(G[j], G[j-1]);
        
            FOR(j, 0, Fn) {
                int t = k - j - rt;
                checkMax(ans, F[j] + (t<Gn?G[t]:G[Gn-1]));
            }
            checkMax(Fn, Gn); REP(j, Fn) checkMax(F[j], G[j]);
          
            //REP(i, Gn) G[i] = 0;
            fill(G, G+Gn, 0);
        }
    
        //REP(i, Fn) F[i] = 0;
        fill(F, F+Fn, 0);
    }
    
    Ln = 0;
}

inline void solve(int u = 1){
    
    _c = INF, find_center(u, 0), u = c;    
    dep[u] = dist[u] = 0, dfs1(u, 0), 
    
    stat(isBlack[u]);
    
    for(int i=hd[u];i;i=suc[i]){
        n_ = sz[v], solve(v);
    }
}


int main(){

    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //ios::sync_with_stdio(false);
    
    RD(n, k, m); DO(m) isBlack[RD()] = true;
    
    for (int i=2;i<n<<1;++i){
        RD(a[i], b[i]); RD_S(w[i]), a[i|1] = b[i], b[i|1] = a[i], w[i|1] = w[i];
        prd[hd[a[i]]] = i, suc[i] = hd[a[i]], hd[a[i]] = i; ++i;
        prd[hd[a[i]]] = i, suc[i] = hd[a[i]], hd[a[i]] = i;
    }
        
    n_ = n, solve(), printf("%d\n", ans);
}

External link:

http://www.spoj.pl/problems/FTOUR2/

Posted by xiaodao
Category: SPOJ