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);
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9769718.html
相关资源：JAVA上百实例源码以及开源项目
