CF258E Little Elephant and Tree

little_sun · 2021-09-06 22:50:36 · 题解

题目大意

你有一棵有 n 个节点的有根（根为 1 ）树，你要对对其进行 m 次操作。

每次操作给出两个数 a_i, b_i，你要往以 a_i, b_i 为根的子树内每个点的集合里加入数 i。

问最后对于每个点有多少个点（不包括自己）的集合与其交集非空。

题目分析

将树按照 \texttt{DFS} 序遍历，则子树对应于一段连续的区间。

现在的操作就相当于 给出两个区间 [a,b],[l,r]，这两个区间并集内的所有节点都变得两两关联。

关联关系的定义中涉及两个节点，因此考虑两维，第一维表示关联定义中的 第一个节点，而第二维表示关联定义中的第二个节点，两维考虑的范围都是树上 所有的节点，那么操作就相当于说，使得第一维当中的所有编号[a,b],[l,r] 中 的点与第二维中所有编号为 [a,b],[l,r] 中的点互相关联。

这个问题可以将每个操作拆成 4 个矩形，使用矩形面积并的方式用扫描线+线段树解决。

代码

#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprintf(stderr, cat)

const int MaxN = 2e5 + 10;

struct edge
{
    int next, to;
} e[MaxN << 1];

struct node
{
    int l, r;
    int sum, len;
};

struct query
{
    int pos, l, r, c;
} Q[MaxN << 2];

int n, m, q, cnt, now, dfscnt, ans[MaxN];
int head[MaxN], dfn[MaxN], siz[MaxN];

struct SegmentTree
{
    node t[MaxN << 2];
    void build(int id, int l, int r)
    {
        t[id].l = l, t[id].r = r;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void pushup(int id)
    {
        int l = t[id].l, r = t[id].r;
        if (t[id].sum) t[id].len = r - l + 1;
        else
            t[id].len = t[id << 1].len + t[id << 1 | 1].len;
    }
    void modify(int id, int l, int r, int val)
    {
        if (t[id].r < l || r < t[id].l)
            return;
        if (l <= t[id].l && t[id].r <= r)
        {
            t[id].sum += val, pushup(id);
            return;
        }
        modify(id << 1, l, r, val);
        modify(id << 1 | 1, l, r, val), pushup(id);
    }
} T;

int cmp(query a, query b) { return a.pos < b.pos; }

void add(int a, int b, int l, int r)
{
    Q[++q] = (query){a, l, r, 1};
    Q[++q] = (query){b + 1, l, r, -1};
    // meow("$ %d %d %d %d\n", a, b, l, r);
}

void add_edge(int u, int v)
{
    ++cnt;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

inline int read()
{
    int x = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0')
        ch = getchar();
    while(ch <= '9' && ch >= '0') 
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

void dfs(int u, int fa)
{
    dfn[u] = ++dfscnt, siz[u] = 1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v, u), siz[u] += siz[v];
    }
}

signed main()
{   
    n = read(), m = read(), T.build(1, 1, n);
    for(int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        add_edge(u, v), add_edge(v, u);
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i++)
    {
        int a, b, l, r;
        a = read(), b = dfn[a] + siz[a] - 1, a = dfn[a];
        l = read(), r = dfn[l] + siz[l] - 1, l = dfn[l];
        add(a, b, a, b), add(a, b, l, r);
        add(l, r, a, b), add(l, r, l, r);
    }
    std::sort(Q + 1, Q + q + 1, cmp), now = 1;
    for(int i = 1; i <= n; i++)
    {
        while(now <= q && Q[now].pos == i)
            T.modify(1, Q[now].l, Q[now].r, Q[now].c), ++now;
        ans[i] = T.t[1].len, ans[i] ? --ans[i] : 0;
    }
    for(int i = 1; i <= n; i++)
        printf("%d ", ans[dfn[i]]);
    return 0;
}