poj 3417 Network(tarjan lca)

先给出一棵无根树，然后下面再给出m条边，把这m条边连上，然后每次你能毁掉两条边，规定一条是树边，一条是新边，问有多少种方案能使树断裂。

我们设添加了一条新边后，树形成了一个环，表示为x->y->lca(x,y)，我们将其中的边都覆盖一次。添加了多条新边后，可知树上有些边是会被多次覆盖的，画图很容易发现，但一个树边被覆盖了2次或以上，它就是一条牢固的边，就是说毁掉它再毁掉任何一条新边都好，树都不会断裂。所以我们只要统计被覆盖过零次或一次的边即可。覆盖过零次的边，拆掉以后还能再拆任意一条新边，所以cnt+=m。覆盖过一次的边，拆掉后必须拆掉覆盖它的那个边，所以cnt++。剩下的就是求lca了。然而用nlogn的lca求法居然会超时。。所以只能用tarjan。

#include <cctype>

#include <cstdio>

using namespace std;

const int maxn=1e5+5, maxm=1e5+5;

struct Graph{

    struct Edge{

        int to, next; Graph *bel;

        inline int operator *(){ return to; }

        Edge& operator ++(){

            return *this=bel->edge[next]; }

    };

    void addedge(int x, int y){

        Edge &e=edge[++cntedge];

        e.to=y; e.next=fir[x];

        e.bel=this; fir[x]=cntedge;

    }

    Edge& getlink(int x){

        return edge[fir[x]]; }

    Edge edge[maxm*2];

    int cntedge, fir[maxn];

}g, g2;

inline int getint(){

    char c; int re=0, flag=1;

    for (c=getchar(); !isdigit(c); c=getchar())

        if (c=='-') flag=-1;

    for (re=c-48; c=getchar(), isdigit(c); re=re*10+c-48);

    return re*flag;

}

int n, m, visit[maxn], fa[maxn], add[maxn];

long long cnt;

int find(int x){

    return fa[x]==x?x:fa[x]=find(fa[x]);

}

void tarjan(int now, int par){

    Graph::Edge e=g2.getlink(now);

    visit[now]=1;

    for (; *e; ++e) if (visit[*e]){

        add[find(*e)]-=2;

        ++add[now]; ++add[*e];

    }

    e=g.getlink(now);

    //这个要写在后面！不然如果这个点的lca在它子树里，会算两遍

    for (; *e; ++e){

        if (*e==par) continue;

        tarjan(*e, now);

        fa[*e]=now;

    }

}

int dfs(int now, int par){ //断开now上面的边

    int v=add[now]; Graph::Edge e=g.getlink(now);

    for (; *e; ++e){

        if (*e==par) continue;

        v+=dfs(*e, now);

    }

    if (now!=1){

        if (v==0) cnt+=m;

        if (v==1) ++cnt;

    }

    return v;

}

int main(){

    scanf("%d%d", &n, &m); int x, y;

    for (int i=1; i<=n; ++i) fa[i]=i;

    for (int i=1; i<n; ++i){

        x=getint(); y=getint();

        g.addedge(x, y); g.addedge(y, x);

    }

    for (int i=1; i<=m; ++i){

        x=getint(); y=getint();

        if (x==y){ continue; }

        g2.addedge(x, y);

        g2.addedge(y, x);

    }

    tarjan(1, 0); dfs(1, 0);

    printf("%lld\n", cnt);

    return 0;

}

巴特西

poj 3417 Network(tarjan lca)

poj 3417 Network(tarjan lca)

最新文章

热门文章