Loading [MathJax]/extensions/tex2jax.js

P4556:「Vani有约会」雨天的尾巴题解

主要思路

这道题可以离线回答,很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息,然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG,但是我们可以动态开点,然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的,这样空间就可以接受的了。

既然有了很好用的动态开点线段树,我们就可以用树上差分那一套路,在端点和\(LCA\)处打标记,然后考虑从下往上合并答案。合并可以用线段树合并,复杂度为重合部分,差不多就是\(O(\log n)\)。然后就没了,很傻逼的一道题。

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// P4556.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100010;
struct node
{
int lson, rson, val, max_pos;
} tree[MAX_N * 60];
int ptot, n, m, head[MAX_N], current, fa[21][MAX_N], dep[MAX_N], roots[MAX_N];
int answer[MAX_N], us[MAX_N], vs[MAX_N], wes[MAX_N], range;
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void pushup(int p)
{
if (tree[tree[p].rson].val <= tree[tree[p].lson].val)
tree[p].val = tree[tree[p].lson].val, tree[p].max_pos = tree[tree[p].lson].max_pos;
else
tree[p].val = tree[tree[p].rson].val, tree[p].max_pos = tree[tree[p].rson].max_pos;
return;
}
int update(int qx, int l, int r, int p, int val)
{
if (p == 0)
p = ++ptot;
if (l == r)
{
tree[p].val += val, tree[p].max_pos = l;
return p;
}
int mid = (l + r) >> 1;
if (qx <= mid)
tree[p].lson = update(qx, l, mid, tree[p].lson, val);
else
tree[p].rson = update(qx, mid + 1, r, tree[p].rson, val);
pushup(p);
return p;
}
int merge(int p, int pre, int l, int r)
{
if (p == 0)
return pre;
if (pre == 0)
return p;
if (l == r)
{
tree[p].val += tree[pre].val;
tree[p].max_pos = l;
return p;
}
int mid = (l + r) >> 1;
tree[p].lson = merge(tree[p].lson, tree[pre].lson, l, mid);
tree[p].rson = merge(tree[p].rson, tree[pre].rson, mid + 1, r);
pushup(p);
return p;
}
int getLCA(int x, int y)
{
if (dep[x] < dep[y])
swap(x, y);
for (int i = 20; i >= 0; i--)
if (dep[fa[i][x]] >= dep[y])
x = fa[i][x];
if (x == y)
return x;
for (int i = 20; i >= 0; i--)
if (fa[i][x] != fa[i][y])
x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
void dfs1(int u)
{
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa[0][u])
{
dep[edges[i].to] = dep[u] + 1, fa[0][edges[i].to] = u;
dfs1(edges[i].to);
}
}
void dfs2(int u)
{
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (fa[0][u] != edges[i].to)
dfs2(edges[i].to), roots[u] = merge(roots[u], roots[edges[i].to], 1, range);
if (tree[roots[u]].val != 0)
answer[u] = tree[roots[u]].max_pos;
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i <= n - 1; i++)
scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
dep[1] = 1, dfs1(1);
for (int i = 1; i <= 20; i++)
for (int j = 1; j <= n; j++)
fa[i][j] = fa[i - 1][fa[i - 1][j]];
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &us[i], &vs[i], &wes[i]), range = max(range, wes[i]);
for (int i = 1; i <= m; i++)
{
int u = us[i], v = vs[i], w = wes[i];
roots[u] = update(w, 1, range, roots[u], 1);
roots[v] = update(w, 1, range, roots[v], 1);
int lca = getLCA(u, v);
roots[lca] = update(w, 1, range, roots[lca], -1);
if (fa[0][lca])
roots[fa[0][lca]] = update(w, 1, range, roots[fa[0][lca]], -1);
continue;
}
dfs2(1);
for (int i = 1; i <= n; i++)
printf("%d\n", answer[i]);
return 0;
}
// P4556.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 100010; struct node { int lson, rson, val, max_pos; } tree[MAX_N * 60]; int ptot, n, m, head[MAX_N], current, fa[21][MAX_N], dep[MAX_N], roots[MAX_N]; int answer[MAX_N], us[MAX_N], vs[MAX_N], wes[MAX_N], range; struct edge { int to, nxt; } edges[MAX_N << 1]; void addpath(int src, int dst) { edges[current].to = dst, edges[current].nxt = head[src]; head[src] = current++; } void pushup(int p) { if (tree[tree[p].rson].val <= tree[tree[p].lson].val) tree[p].val = tree[tree[p].lson].val, tree[p].max_pos = tree[tree[p].lson].max_pos; else tree[p].val = tree[tree[p].rson].val, tree[p].max_pos = tree[tree[p].rson].max_pos; return; } int update(int qx, int l, int r, int p, int val) { if (p == 0) p = ++ptot; if (l == r) { tree[p].val += val, tree[p].max_pos = l; return p; } int mid = (l + r) >> 1; if (qx <= mid) tree[p].lson = update(qx, l, mid, tree[p].lson, val); else tree[p].rson = update(qx, mid + 1, r, tree[p].rson, val); pushup(p); return p; } int merge(int p, int pre, int l, int r) { if (p == 0) return pre; if (pre == 0) return p; if (l == r) { tree[p].val += tree[pre].val; tree[p].max_pos = l; return p; } int mid = (l + r) >> 1; tree[p].lson = merge(tree[p].lson, tree[pre].lson, l, mid); tree[p].rson = merge(tree[p].rson, tree[pre].rson, mid + 1, r); pushup(p); return p; } int getLCA(int x, int y) { if (dep[x] < dep[y]) swap(x, y); for (int i = 20; i >= 0; i--) if (dep[fa[i][x]] >= dep[y]) x = fa[i][x]; if (x == y) return x; for (int i = 20; i >= 0; i--) if (fa[i][x] != fa[i][y]) x = fa[i][x], y = fa[i][y]; return fa[0][x]; } void dfs1(int u) { for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].to != fa[0][u]) { dep[edges[i].to] = dep[u] + 1, fa[0][edges[i].to] = u; dfs1(edges[i].to); } } void dfs2(int u) { for (int i = head[u]; i != -1; i = edges[i].nxt) if (fa[0][u] != edges[i].to) dfs2(edges[i].to), roots[u] = merge(roots[u], roots[edges[i].to], 1, range); if (tree[roots[u]].val != 0) answer[u] = tree[roots[u]].max_pos; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); for (int i = 1, u, v; i <= n - 1; i++) scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u); dep[1] = 1, dfs1(1); for (int i = 1; i <= 20; i++) for (int j = 1; j <= n; j++) fa[i][j] = fa[i - 1][fa[i - 1][j]]; for (int i = 1; i <= m; i++) scanf("%d%d%d", &us[i], &vs[i], &wes[i]), range = max(range, wes[i]); for (int i = 1; i <= m; i++) { int u = us[i], v = vs[i], w = wes[i]; roots[u] = update(w, 1, range, roots[u], 1); roots[v] = update(w, 1, range, roots[v], 1); int lca = getLCA(u, v); roots[lca] = update(w, 1, range, roots[lca], -1); if (fa[0][lca]) roots[fa[0][lca]] = update(w, 1, range, roots[fa[0][lca]], -1); continue; } dfs2(1); for (int i = 1; i <= n; i++) printf("%d\n", answer[i]); return 0; }
// P4556.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100010;

struct node
{
    int lson, rson, val, max_pos;
} tree[MAX_N * 60];

int ptot, n, m, head[MAX_N], current, fa[21][MAX_N], dep[MAX_N], roots[MAX_N];
int answer[MAX_N], us[MAX_N], vs[MAX_N], wes[MAX_N], range;

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void pushup(int p)
{
    if (tree[tree[p].rson].val <= tree[tree[p].lson].val)
        tree[p].val = tree[tree[p].lson].val, tree[p].max_pos = tree[tree[p].lson].max_pos;
    else
        tree[p].val = tree[tree[p].rson].val, tree[p].max_pos = tree[tree[p].rson].max_pos;
    return;
}

int update(int qx, int l, int r, int p, int val)
{
    if (p == 0)
        p = ++ptot;
    if (l == r)
    {
        tree[p].val += val, tree[p].max_pos = l;
        return p;
    }
    int mid = (l + r) >> 1;
    if (qx <= mid)
        tree[p].lson = update(qx, l, mid, tree[p].lson, val);
    else
        tree[p].rson = update(qx, mid + 1, r, tree[p].rson, val);
    pushup(p);
    return p;
}

int merge(int p, int pre, int l, int r)
{
    if (p == 0)
        return pre;
    if (pre == 0)
        return p;
    if (l == r)
    {
        tree[p].val += tree[pre].val;
        tree[p].max_pos = l;
        return p;
    }
    int mid = (l + r) >> 1;
    tree[p].lson = merge(tree[p].lson, tree[pre].lson, l, mid);
    tree[p].rson = merge(tree[p].rson, tree[pre].rson, mid + 1, r);
    pushup(p);
    return p;
}

int getLCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (dep[fa[i][x]] >= dep[y])
            x = fa[i][x];
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
        if (fa[i][x] != fa[i][y])
            x = fa[i][x], y = fa[i][y];
    return fa[0][x];
}

void dfs1(int u)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[0][u])
        {
            dep[edges[i].to] = dep[u] + 1, fa[0][edges[i].to] = u;
            dfs1(edges[i].to);
        }
}

void dfs2(int u)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (fa[0][u] != edges[i].to)
            dfs2(edges[i].to), roots[u] = merge(roots[u], roots[edges[i].to], 1, range);
    if (tree[roots[u]].val != 0)
        answer[u] = tree[roots[u]].max_pos;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dep[1] = 1, dfs1(1);
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &us[i], &vs[i], &wes[i]), range = max(range, wes[i]);
    for (int i = 1; i <= m; i++)
    {
        int u = us[i], v = vs[i], w = wes[i];
        roots[u] = update(w, 1, range, roots[u], 1);
        roots[v] = update(w, 1, range, roots[v], 1);
        int lca = getLCA(u, v);
        roots[lca] = update(w, 1, range, roots[lca], -1);
        if (fa[0][lca])
            roots[fa[0][lca]] = update(w, 1, range, roots[fa[0][lca]], -1);
        continue;
    }
    dfs2(1);
    for (int i = 1; i <= n; i++)
        printf("%d\n", answer[i]);
    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *