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)
原文地址：http://www.cnblogs.com/MyNameIsPc/p/8000120.html