poj 3417 Network 【LCA】【树中增新边后 求每条树边被环所覆盖的次数】

Description

Input

Output

Sample Input

4 1
1 2
2 3
1 4
3 4

Sample Output

3

题意：给你一个N个点构成的树（N-1条边），又给你M条新边。现在要求你破坏一条树边和一条新边使得树分成两个部分。问这样的方案有多少种。

分析：树是无环的，在增加新边后必定成环。

这样对于每条边，根据它被环覆盖的情况可以分为三类

一，覆盖次数为0，显然只要破坏这条边就完成任务了，但题目还要求破坏一条新边。这样的话显然有M种方案（有M条新边嘛）。

二，覆盖次数为1（说明它所在环中只增加了一条新边），这样我们仅仅破坏它一条边是不够的，还要把它所在环中的新边破坏掉。这样的话方案只有一种。

三：覆盖次数大于1（说明它所在环中不只增加了一条新边），这种情况下，在破坏这条边后还需要破坏掉环中所有的新边，这样破坏新边的条数大于1了，不合题意。因此这种情况下对这条边采取任何措施都是不行的，方案数为0。

这样问题就变成——求出所有边被环覆盖次数。

思路：用num[v]记录<u,v>被覆盖的次数，其中u在DFS树中是v的父节点。

对于每条新加入的边<u,v>，有 num[u]++，num[v]++，num[LCA(u,v)] -= 2。这样处理是为了方便自底向上计算num值。因为对于LCA(u, v)的num值，自底向上计算num值时，我们必然会加上num[u]和num[v]的值，为了除去多算的num值，LCA(u, v)当然要减2。给个图，务必自己模拟下。

如图所示：<4,5>新加的边，LCA(4, 5) = 2.

num[4] = num[5] = 1, num[2] = -2;

DFS(2)时，遍历到4和5回溯的时候，num[2] += num[4]，num[2] += num[5]。

LCA的求法还是用 LCA转RMQ 实现的。

LCA转RMQ模板看这里：看模板点我

AC代码：提醒 用vector建图会TLE。

#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#define MAXN 100000+10
#define MAXM 200000+10
using namespace std;
struct Edge
{
int from, to, next;
};
Edge edge[MAXM];
int head[MAXN], edgenum;
int vs[MAXN<<1], depth[MAXN<<1];
int id[MAXN];
int dfs_clock;
int N, M;
//vector<int> G[MAXN];
void init()
{
edgenum = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v)
{
Edge E = {u, v, head[u]};
edge[edgenum] = E;
head[u] = edgenum++;
}
void getMap()
{
int a, b;
for(int i = 1; i < N; i++)
scanf("%d%d", &a, &b), addEdge(a, b), addEdge(b, a);
//G[a].push_back(b);
//G[b].push_back(a);
}
int dp[MAXN<<1][30];
void RMQ_init(int NN)
{
for(int i = 1; i <= NN; i++)
dp[i][0] = i;
for(int j = 1; (1<<j) <= NN; j++)
{
for(int i = 1; i + (1<<j) - 1 <= NN; i++)
{
int a = dp[i][j-1];
int b = dp[i+(1<<(j-1))][j-1];
if(depth[a] < depth[b])
dp[i][j] = a;
else
dp[i][j] = b;
}
}
}
int query(int L, int R)
{
int k = 0;
while((1<<(k+1)) <= R-L+1) k++;
int a = dp[L][k];
int b = dp[R-(1<<k)+1][k];
if(depth[a] < depth[b])
return a;
else
return b;
}
int LCA(int u, int v)
{
int x = id[u];
int y = id[v];
if(x < y)
return vs[query(x, y)];
else
return vs[query(y, x)];
}
void DFS(int u, int fa, int d)
{
id[u] = dfs_clock;
vs[dfs_clock] = u;
depth[dfs_clock++] = d;
for(int i = head[u]; i != -1; i = edge[i].next)
//for(int i = 0; i < G[u].size(); i++)
{
//int v = G[u][i];
int v = edge[i].to;
if(v == fa) continue;
DFS(v, u, d+1);
vs[dfs_clock] = u;
depth[dfs_clock++] = d;
}
}
void find_depth()
{
memset(vs, 0, sizeof(vs));
memset(depth, 0, sizeof(depth));
memset(id, 0, sizeof(id));
dfs_clock = 1;
DFS(1, -1, 0);
}
int num[MAXN];//num[v]记录<u,v>被环覆盖次数
void worknum(int u, int fa)
{
for(int i = head[u]; i != -1; i = edge[i].next)
//for(int i = 0; i < G[u].size(); i++)
{
//int v = G[u][i];
int v = edge[i].to;
if(v == fa) continue;
worknum(v, u);
num[u] += num[v];
}
}
void solve()
{
find_depth();
RMQ_init(dfs_clock - 1);
memset(num, 0, sizeof(num));
for(int i = 1; i <= M; i++)//新边
{
int a, b;
scanf("%d%d", &a, &b);
num[a]++;
num[b]++;
num[LCA(a, b)] -= 2;
}
worknum(1, -1);//计算所有树边的num值
int ans = 0;
for(int i = 2; i <= N; i++)
{
if(num[i] == 0)//树边没有被覆盖
ans += M;
else if(num[i] == 1)//树边被覆盖一次
ans += 1;
}
printf("%dn", ans);
}
int main()
{
while(scanf("%d%d", &N, &M) != EOF)
{
init();
getMap();
solve();
}
return 0;
}

最后

以上就是幸福缘分为你收集整理的poj 3417 Network 【LCA】【树中增新边后 求每条树边被环所覆盖的次数】的全部内容，希望文章能够帮你解决poj 3417 Network 【LCA】【树中增新边后 求每条树边被环所覆盖的次数】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。