xiaoMa
"Bye Bye Baby Blue"
树上差分(POJ-3417)

http://poj.org/problem?id=3417

一颗n−1n−1条主要边的树,然后增加了mm条附加边.
我们只能删除一条主要边,一条附加边,一种边叫做主要边,一种边叫做附加边.
要求删除两条边后,这棵树不再是连通的.

对于每一条连接x,y节点的(x,y),其实我们都可以认为这条边,连接了(x,y)这条路径上的所有点.
当没有了主要边的时候,其实附加边就是我们的主要边.
所以说,附加边(x,y),就是将树上x,y之间的路径上的每条主要边,都覆盖了一次.
因为当(x,y)(x,y)路径上的任意一条主要边消失后,他都可以成为主要边,去维护连通性.
因此现在我们的问题模型转化了.
给定一个n−1条边的树,求每一条树边,被非树边覆盖了多少次
树边也就是主要边
非树边也就是附加边
那么这就是一个树上差分统计覆盖次数问题了.
每一条附加边,使得(x,y)节点的路径上,路径上的每一条主要边的权值+1.

前置技能树 差分+LCA ,时间复杂度是O(n+m),听说树链剖分也可以做,逃。。

刚才服务器差点又炸了,幸好有数据库的备份。

300ms还是比较快的😀
/** 
 * KUANGBIN___POJ_3417_LCA_CHAFEN_CPP
 * @author : MaWeiTao 
 *
 */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <cctype>

#define FAST_IO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define sca(a) scanf("%d",&amp;a);
#define sca2(a, b) scanf("%d%d",&amp;a,&amp;b)
#define sca3(a, b, c) scanf("%d%d%d",&amp;a,&amp;b,&amp;c)
#define scac(a) scanf("%c",a);
#define scacc(a, b) scanf("%c%c",a,b)
#define mem(a, b) memset(a,b,sizeof(a))
using namespace std;
template<class T>void tomax(T &amp;a, T b) { a = max(a, b); }
template<class T>void tomin(T &amp;a, T b) { a = min(a, b); }
typedef long long ll;
typedef pair<int, int> pii;

const int N = 100005;
int n, m, t = 0, head[N], v[N], ans = 0;
int a[N][20] = {}, deg[N] = {}, fa[N];
struct Edge {
    int y, next;
} e[N * 2];
void add(int x, int y) {
    e[++t].y = y;
    e[t].next = head[x];
    head[x] = t;
}
inline int read() {
    char c = getchar();
    int a = 0;
    int aa = 1;
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            aa = -1;
    for (; c >= '0' &amp;&amp; c <= '9'; c = getchar()) a = (a * 10) + c - 48;
    return aa * a;
}
void dfs1(int x, int f)  //求LCA
{
    a[x][0] = f;
    for (register int i = 1; i <= 17; i++) a[x][i] = a[a[x][i - 1]][i - 1];
    for (register int i = head[x]; i; i = e[i].next) {
        int y = e[i].y;
        if (y == f)
            continue;
        deg[y] = deg[x] + 1;
        dfs1(y, x);
    }
}
void dfs2(int x, int f)  //求fa[]数组,统计答案
{
    fa[x] = v[x];  //差分数组赋值给 边权数组fa
    for (register int i = head[x]; i; i = e[i].next) {
        int y = e[i].y;
        if (y == f)
            continue;
        dfs2(y, x);
        fa[x] += fa[y];  //一直搜索下去,
    }
    //如果f[x]==2,无论怎么切都不行
    if (fa[x] == 1 &amp;&amp; x != 1)
        ans++;
    //如果f[x]==1,则切这条边后,只要再切与这条边相连的非树边就能为答案贡献1
    if (fa[x] == 0 &amp;&amp; x != 1)
        ans += m;
    //如果f[x]==0,则切这条边后,无论再切哪一条边,都可以为答案贡献m
}
int lca(int x, int y) {
    if (deg[y] > deg[x])
        swap(x, y);
    int tmp = deg[x] - deg[y];
    for (register int i = 0; i<=17; i++)
        if ((1<<i) &amp; tmp)
            x = a[x][i];
    if (x == y)
        return x;
    for (register int i = 17; i>=0; i--)
        if (a[x][i] != a[y][i])
            x = a[x][i], y = a[y][i];
    return a[x][0];
}
int main() {
    //	freopen("yam2.in","r",stdin);
    //	freopen("yam.out","w",stdout);
    n = read();
    m = read();
    int x, y;
    for (register int i = 1; i < n; i++) {
        x = read();
        y = read();
        add(x, y);
        add(y, x);
    }
    dfs1(1, 0);
    for (register int i = 1; i <= m; i++) {
        x = read();
        y = read();
        v[x]++;
        v[y]++;
        v[lca(x, y)] -= 2;
    }
    dfs2(1, 0);
    printf("%d\n", ans);
    return 0;
}

发表评论

textsms
account_circle
email

树上差分(POJ-3417)
http://poj.org/problem?id=3417 一颗n−1n−1条主要边的树,然后增加了mm条附加边. 我们只能删除一条主要边,一条附加边,一种边叫做主要边,一种边叫做附加边. 要求删除两条边后,这…
扫描二维码继续阅读
2020-03-08