POJ3417：http://poj.org/problem?id=3417
思路
我们注意到由“主要边”构成一颗树 “附加边”则是非树边 把一条附加边(x,y)加入树中 会与树上x,y之间构成一个环
因此 我们称每条附加边(x,y)都把树上x,y之间的路径覆盖一次 我们只需要统计出每条“主要边”被覆盖几次
有以下几种情况
- 第一步把覆盖0次的主要边切断 则第二步可以任意切一条附加边 ans+=m
- 第一步把覆盖1次的主要边切断 则第二步只有一种选择切附加边 ans+=1
- 第一步把覆盖2次或以上的主要边切断 则不可能击败Dark
这样我们就可以统计出ans
解决每条边的覆盖次数 需要用到树上差分算法
我们给每个节点初值为0
对于每条附加边(x,y) 我们给x和y节点权值+1
对于x和y的lca节点权值-2（想想为什么）
设F(x)为以x为根的子树中各节点的权值和 则F(x)就是x与其父节点之间树边被覆盖的次数
最后统计ans即可
PS：这题需要把cin cout 改为scanf printf 不然会TLE 坑了我一晚上
代码
#include<iostream> #include<cstdio> #include<cmath> using namespace std; #define maxn 100010 int n,m,cnt,ans; int h[maxn],dep[maxn],f[maxn][31],vis[maxn]; struct Edge { int next; int to; }e[maxn<<1]; void add(int u,int v) { e[++cnt].to=v; e[cnt].next=h[u]; h[u]=cnt; } void deal(int u,int fa) { dep[u]=dep[fa]+1;//深度等于父节点+1 for(int i=1;i<=20;i++)//枚举倍增步数 { f[u][i]=f[f[u][i-1]][i-1];//二分思想 } for(int i=h[u];i;i=e[i].next) { int v=e[i].to; if(v==fa) continue;//如果是父节点跳过 f[v][0]=u;//如果是子节点 deal(v,u); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y);//保证x的深度大 for(int i=20;i>=0;i--)//从大开始枚举 { if(dep[f[x][i]]>=dep[y]) x=f[x][i];//先跳到同一层 if(x==y) return x;//如果已经找到 } for(int i=20;i>=0;i--)//此时x y已经在同一层 { if(f[x][i]!=f[y][i])//如果不同就继续跳 { x=f[x][i]; y=f[y][i]; } } return f[x][0]; } void dp(int x) { for(int i=h[x];i;i=e[i].next) { int v=e[i].to; if(v==f[x][0]) continue; dp(v);//不是父亲时 继续找 vis[x]+=vis[v];//递归回来时加上所有节点的权值 } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b);//无向图 add(b,a); } deal(1,0);//预处理 for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); vis[a]++;//树上差分算法 vis[b]++; vis[lca(a,b)]-=2; } dp(1);//计算所有主要边被覆盖几次 for(int i=2;i<=n;i++)//从2开始是因为我们把点存成边 { if(vis[i]==0)//被覆盖0次 ans+=m; if(vis[i]==1)//被覆盖1次 ans++; } printf("%d",ans); }