http://www.lydsy.com/JudgeOnline/problem.php?id=3648
http://hi.baidu.com/greencloud/item/5d009dddcecde7b133db90ad

Brief description:

给定一个树加一条边。。求这个图中所有经过结点树 >= k 的路径有多少组。。
（(u -> v) 与 (v -> u) 算一组。。）

Analysis:

树的情况树分治即可。。。由于都是单位权。。。我们树状数组即可。。基本功。。。

考虑环的情况。。。比如样例。。。。
我们沿顺时针转三次。。。（注意 (u, v) 和 (v, u) 只统计一次。。而他们正好分别对应一次顺时针和一次逆时针。、、）
这里 d 是 offset。。。

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9, M = N*2;

namespace BIT{
    const int N = ::N+::N+1;
    int C[N], n;
    void Add(int x, int d = 1){
        x += ::N;
        for (;x<N;x+=low_bit(x)) C[x] += d;
    }
    int Sum(int x){
        x += ::N;
        int res = 0; for (;x;x^=low_bit(x)) res += C[x];
        return res;
    }
    int Rsum(int x){
        int t = Sum(::N); t -= x + ::N > 0 ? Sum(x) : 0;
        return t;
    }
} //using namespace BIT;


int hd[N], prd[M], suc[M], to[M];
int m;

void add_edge(int a, int b){
    to[m] = b, suc[prd[hd[a]] = m] = hd[a], hd[a] = m++;
}

void add_edgee(int a, int b) {
    add_edge(a, b);
    add_edge(b, a);
}

#define aa to[i^1]
#define bb to[i]
#define v bb

inline void del(int i){
    if (hd[aa] == i) prd[hd[aa] = suc[i]] = 0;
    else prd[suc[i]] = prd[i], suc[prd[i]] = suc[i];
}

inline void rsm(int i){
    if (suc[i] == hd[aa]) hd[aa] = i;
    prd[suc[i]] = suc[prd[i]] = i;
}

inline void dell(int i){
    del(i), del(i^1);
}

inline void rsmm(int i){
    rsm(i), rsm(i^1);
}

int n, k; int sz[N], dep[N]; LL ans; VI L;

void Scann(int u, int p) {
    L.PB(dep[u]); REP_G(i, u) if (v != p){
        dep[v] = dep[u] + 1;
        Scann(v, u);
    }
}

void Scan(int u){
    CLR(L); dep[u] = 1; L.PB(dep[u]);
    REP_G(i, u){
        dep[v] = dep[u] + 1;
        Scann(v, u);
    }
}

namespace TDC{

    int nn, cc, c;

    void dfsc(int u, int p = 0){
        int ss = 0; sz[u] = 1; REP_G(i, u) if (v != p){
            dfsc(v, u), sz[u] += sz[v];
            checkMax(ss, sz[v]);
        }
        checkMax(ss, nn - sz[u]);
        if (ss <= cc) cc = ss, c = u;
    }

    void dfs0(int u, int p = -1){
        sz[u] = 1; REP_G(i, u) if (v != p){
            dep[v] = dep[u] + 1;
            dfs0(v, u);
            sz[u] += sz[v];
        }
    }

    void dfs1(int u, int p){
        L.PB(dep[u]);
        REP_G(i, u) if (v != p){
            dfs1(v, u);
        }
    }

    void dfs2(int u, int p = -1){
        BIT::Add(dep[u], -1);
        REP_G(i, u) if (v != p){
            dfs2(v, u);
        }
    }

    void gao(int u = 1){

        cc = INF, dfsc(u), u = c;

        dep[u] = 1; dfs0(u); BIT::Add(1);

        REP_G(i, u){
            CLR(L); dfs1(v, u);
            ECH(it, L) ans += BIT::Rsum(k-*it);
            ECH(it, L) BIT::Add(*it);
        }

        dfs2(u);

        REP_G(i, u){
            nn = sz[v], dell(i), gao(v), rsmm(i);
        }
    }
}


VI Circle; PII sta[N]; int pos[N], top = 0;

void dfs(int u = 1, int p = -1){ // Find_Circle
    sta[pos[u]=++top].fi = u;
    REP_G(i, u) if (i != (p^1)){
        sta[top].se = i;
        if (!pos[v]) dfs(v, i);
        else {
            FOR_1(ii, pos[v], top) {
                Circle.PB(sta[ii].fi);
                dell(sta[ii].se);
            }
        }
    }
    --top;
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    m = 2; int m; RD(n, m, k); DO(m){
        int a, b; RD(a, b);
        add_edgee(a, b);
    }

    if (m == n-1) TDC::gao();
    else {

        dfs(); ECH(c, Circle) TDC::gao(*c);

        int d = 0;

        ECH(c, Circle){
            Scan(*c);
            ECH(it, L) BIT::Add(*it-d);
            ++d;
        }

        ECH(c, Circle){
            Scan(*c);
            ECH(it, L) BIT::Add(*it-d+SZ(Circle), -1);
            ECH(it, L) ans += BIT::Rsum(k-d-*it);
            ECH(it, L) BIT::Add(*it-d);
            ++d;
        }

        ECH(c, Circle){
            Scan(*c);
            ECH(it, L) BIT::Add(*it-d+SZ(Circle), -1);
            ++d;
        }
    }

    printf("%lld\n", ans);
}

https://gist.github.com/lychees/6b55943725966850b1a3

Posted by xiaodao
Category: 日常