主要是记录思路，不要被刚开始错误方向带偏了 www

「CF1110F」Nearest Leaf

特殊性质：先序遍历即为 \(1 \to n\)，可得出：叶子节点编号递增或可在不改变树形态的基础上调整为递增。

这样就可找出区间 \([l, r]\) 中的叶子节点有哪些了，预处理深度，暴力 \(O(n ^ 2)\)。

考虑柿子 \(\min \{\mathrm{d} (y) - \mathrm{d} (\mathrm{f} (x))\}\)，其中 \(d(x)\) 表示深度，\(f(x)\) 表示父亲，\(y\) 为枚举的叶子，\(x\) 为定点。

要使答案最小，即求 \(\min \{\mathrm{d}(y)\}\)，这不线段树？？？哦 GG，区间 \([l, r]\) 显然有可能在定点 \(x\) 子树外。

那如果我们把离线询问挂树上，考虑动态维护线段树，保证遍历到一个节点时，线段树的长相是正确的，好像就能做了？即：

  • 遇到一个节点，我们就把子树内 \(-\)，子树外 \(+\)，然后直接处理查询。
  • 线段树维护区间加和区间最小值。
  • 注意极大值的取值，注意回溯的时候要复原。

过了。

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

typedef long long LL;

LL Abs (LL x) { return x < 0 ? -x : x; }

LL Max (LL x, LL y) { return x > y ? x : y; }

LL Min (LL x, LL y) { return x < y ? x : y; }

int Read () {

    int x = 0, k = 1;

    char s = getchar ();

    while (s < '0' || s > '9') {

        if (s == '-')

            k = -1;

        s = getchar ();

    }

    while ('0' <= s && s <= '9')

        x = (x << 3) + (x << 1) + (s ^ 48), s = getchar ();

    return x * k;

}

void Write (LL x) {

    if (x < 0)

        putchar ('-'), x = -x;

    if (x > 9)

        Write (x / 10);

    putchar (x % 10 + '0');

}

void Print (LL x, char s) { Write (x), putchar (s); }

const LL Inf = 1e16;

const int Maxn = 5e5 + 5;

struct Segment_Tree {

    struct Segment_Node {

        int l, r;

        LL Lazy, Val;

#define Lson p << 1

#define Rson p << 1 | 1

        Segment_Node () {}

        Segment_Node (int L, int R, LL La, LL V) { l = L, r = R, Lazy = La, Val = V; }

    } Tr[Maxn << 2];

    void Make_Tree (int p, int l, int r) {

        Tr[p].Val = Inf, Tr[p].l = l, Tr[p].r = r, Tr[p].Lazy = 0;

        if (l == r)

            return ;

        int Mid = (l + r) >> 1;

        Make_Tree (Lson, l, Mid), Make_Tree (Rson, Mid + 1, r);

    }

    void Pull (int p) { Tr[p].Val = Min (Tr[Lson].Val, Tr[Rson].Val); }

    void Push (int p) {

        if (Tr[p].Lazy) {

            Tr[Lson].Val += Tr[p].Lazy, Tr[Rson].Val += Tr[p].Lazy;

            Tr[Lson].Lazy += Tr[p].Lazy, Tr[Rson].Lazy += Tr[p].Lazy;

            Tr[p].Lazy = 0;

        }

    }

    void Update (int p, int l, int r, LL x) {

        if (l <= Tr[p].l && Tr[p].r <= r) {

            Tr[p].Lazy += x, Tr[p].Val += x;

            return ;

        }

        Push (p);

        int Mid = (Tr[p].l + Tr[p].r) >> 1;

        if (l <= Mid)

            Update (Lson, l, r, x);

        if (r > Mid)

            Update (Rson, l, r, x);

        Pull (p);

    }

    LL Query (int p, int l, int r) {

        if (l <= Tr[p].l && Tr[p].r <= r)

            return Tr[p].Val;

        Push (p);

        LL Res = Inf;

        int Mid = (Tr[p].l + Tr[p].r) >> 1;

        if (l <= Mid)

            Res = Min (Res, Query (Lson, l, r));

        if (r > Mid)

            Res = Min (Res, Query (Rson, l, r));

        return Res;

    }

#undef Lson

#undef Rson

} Tree;

struct Query {

    int l, r, Id;

    Query () {}

    Query (int L, int R, int I) { l = L, r = R, Id = I; }

};

struct Edge {

    int v, w;

    Edge () {}

    Edge (int V, int W) { v = V, w = W; }

    friend bool operator < (Edge x, Edge y) { return x.v < y.v; }

};

int Size[Maxn], n, m;

LL Res[Maxn], Dep[Maxn];

vector <Query> q[Maxn];

vector <Edge> Graph[Maxn];

void Add_Edge (int u, int v, int w) { Graph[u].push_back (Edge (v, w)); }

void Dfs (int u) {

    Size[u] = 1;

    for (int i = 0, v; i < Graph[u].size (); i++)

        v = Graph[u][i].v, Dep[v] = Dep[u] + Graph[u][i].w, Dfs (v), Size[u] += Size[v];

    if (Graph[u].size () == 0)

        Tree.Update (1, u, u, Dep[u] - Inf);

}

void Calc (int u) {

    for (int i = 0; i < q[u].size (); i++)

        Res[q[u][i].Id] = Tree.Query (1, q[u][i].l, q[u][i].r);

    for (int i = 0, v, w; i < Graph[u].size (); i++) {

        v = Graph[u][i].v, w = Graph[u][i].w;

        Tree.Update (1, v, v + Size[v] - 1, -w);

        if (v > 1)

            Tree.Update (1, 1, v - 1, w);

        if (v + Size[v] - 1 < n)

            Tree.Update (1, v + Size[v], n, w);

        Calc (v);

        Tree.Update (1, v, v + Size[v] - 1, w);

        if (v > 1)

            Tree.Update (1, 1, v - 1, -w);

        if (v + Size[v] - 1 < n)

            Tree.Update (1, v + Size[v], n, -w);

    }

}

int main () {

    n = Read (), m = Read ();

    for (int i = 2, p, w; i <= n; i++)

        p = Read (), w = Read (), Add_Edge (p, i, w);

    for (int i = 1; i <= n; i++)

        sort (Graph[i].begin (), Graph[i].end ());

    for (int i = 1, x, l, r; i <= m; i++)

        x = Read (), l = Read (), r = Read (), q[x].push_back (Query (l, r, i));

    Tree.Make_Tree (1, 1, n), Dfs (1), Calc (1);

    for (int i = 1; i <= m; i++)

        Print (Res[i], '\n');

    return 0;

}

「CF633F」The Chocolate Spree

不相交的两条链的最大权值和，难道直接通过直径去扩展？或者直接硬 DP ？

考虑分讨四种情况：Dp[u][0/1/2/3] 分别表示（均在子树内）选了两条链 / 选了一条链 / 选了两条链，其中一条端点是 \(u\) / 选了一条链端点是 \(u\)。

以下转移均考虑遍历顺序（雾。

  • 对于 Dp[u][0]

    • \(v\) 选了两条，直接更新， Dp[u][0] = Max (Dp[u][0], Dp[v][0])
    • \(v\) 选了一条，故 \(u\) 再选一条， Dp[u][0] = Max (Dp[u][0], Dp[v][1] + Dp[u][1])
    • \(v\) 选了两条其中一条端点是 \(v\)，扩展， Dp[u][0] = Max (Dp[u][0], Dp[v][2] + w[u])
    • \(v\) 选了一条且端点是 \(v\)，扩展，Dp[u][0] = Max (Dp[u][0], Dp[v][3] + w[u] + Dp[u][1] - w[u])
    • 可以两条接起来一条，Dp[u][0] = Max (Dp[u][0], Max (Dp[v][2] + Dp[u][3], Dp[u][2] + Dp[v][3])
  • 对于 Dp[u][1]
    • \(v\) 选了一条，直接更新， Dp[u][1] = Max (Dp[u][1], Dp[v][1])
    • \(v\) 选了一条且端点是 \(v\)，扩展， Dp[u][1] = Max (Dp[u][1], Dp[v][3] + w[u])
    • 可以两条接起来，Dp[u][0] = Max (Dp[u][0], Dp[v2][3] + Dp[v2][3] + w[u])
  • 对于 Dp[u][2]
    • \(v\) 选了一条，则 \(u\) 再选一条端点是 \(u\)，Dp[u][2] = Max (Dp[u][2], Dp[v][1] + Dp[u][3])
    • \(v\) 选了两条且其中一条端点是 \(v\)，扩展，Dp[u][2] = Max (Dp[u][2], Dp[v][2] + w[u])
    • \(v\) 选了一条且端点是 \(v\)，扩展然后再选一条，或者不扩展再选一条端点为 \(u\)，Dp[u][2] = Max (Dp[u][2], Max (Dp[v][3] + w[u] + Dp[u][1] - w[u], Dp[v][3] + Dp[u][3]))
  • 对于 Dp[u][3]
    • \(v\) 选了一条且端点是 \(v\)，扩展，Dp[u][3] = Max (Dp[u][3], Dp[v][3] + w[u])

然后一阵删删改改过掉了，或许和上面的整理有点出入？看代码吧。

#include <cstdio>

#include <vector>

using namespace std;

typedef long long LL;

LL Abs (LL x) { return x < 0 ? -x : x; }

LL Max (LL x, LL y) { return x > y ? x : y; }

LL Min (LL x, LL y) { return x < y ? x : y; }

int Read () {

    int x = 0, k = 1;

    char s = getchar ();

    while (s < '0' || s > '9') {

        if (s == '-')

            k = -1;

        s = getchar ();

    }

    while ('0' <= s && s <= '9')

        x = (x << 3) + (x << 1) + (s ^ 48), s = getchar ();

    return x * k;

}

void Write (LL x) {

    if (x < 0)

        putchar ('-'), x = -x;

    if (x > 9)

        Write (x / 10);

    putchar (x % 10 + '0');

}

void Print (LL x, char s) { Write (x), putchar (s); }

const int Maxn = 1e5 + 5;

int w[Maxn];

LL Dp[Maxn][4];

vector <int> Graph[Maxn];

void Add_Edge (int u, int v) { Graph[u].push_back (v), Graph[v].push_back (u); }

void Tree_Dp (int u, int Fa) {

    Dp[u][1] = Dp[u][3] = w[u];

    LL Fir = 0, Sec = 0, Ma = 0;

    for (int i = 0, v; i < Graph[u].size (); i++) {

        v = Graph[u][i];

        if (v == Fa)

            continue;

        Tree_Dp (v, u);

        Dp[u][0] = Max (Dp[u][0], Dp[v][0]);

        Dp[u][0] = Max (Dp[u][0], Dp[v][1] + w[u]);

        Dp[u][0] = Max (Dp[u][0], Dp[v][2] + w[u]);

        Dp[u][0] = Max (Dp[u][0], Dp[v][3] + w[u]);

        if (i > 0) {

            Dp[u][0] = Max (Dp[u][0], Dp[v][1] + Dp[u][1]);

            Dp[u][0] = Max (Dp[u][0], Dp[v][1] + Dp[u][3]);

            if (Ma)

                Dp[u][0] = Max (Dp[u][0], Ma + w[u] + Dp[v][3]);

            Dp[u][0] = Max (Dp[u][0], Dp[v][2] + Dp[u][3]);

            Dp[u][0] = Max (Dp[u][0], Dp[v][3] + Dp[u][1]);

            Dp[u][0] = Max (Dp[u][0], Dp[v][3] + Dp[u][3]);

            Dp[u][0] = Max (Dp[u][0], Dp[v][3] + Dp[u][2]);

        }

        Dp[u][2] = Max (Dp[u][2], Dp[v][1] + w[u]);

        Dp[u][2] = Max (Dp[u][2], Dp[v][2] + w[u]);

        Dp[u][2] = Max (Dp[u][2], Dp[v][3] + w[u]);

        if (i > 0) {

            Dp[u][2] = Max (Dp[u][2], Dp[v][1] + Dp[u][3]);

            if (Ma)

                Dp[u][2] = Max (Dp[u][2], Ma + w[u] + Dp[v][3]);

            Dp[u][2] = Max (Dp[u][2], Dp[v][3] + Dp[u][3]);

        }

        if (Dp[v][1] > Ma)

            Ma = Dp[v][1];

        if (Dp[v][3] > Fir)

            Sec = Fir, Fir = Dp[v][3];

        else if (Dp[v][3] > Sec)

            Sec = Dp[v][3];

        if (Fir && Sec)

            Dp[u][1] = Max (Dp[u][1], Fir + Sec + w[u]);

        Dp[u][1] = Max (Dp[u][1], Dp[v][1]);

        Dp[u][1] = Max (Dp[u][1], Dp[v][3] + w[u]);

        Dp[u][3] = Max (Dp[u][3], Dp[v][3] + w[u]);

    }

}

int main () {

    int n = Read ();

    for (int i = 1; i <= n; i++)

        w[i] = Read ();

    for (int i = 1, u, v; i < n; i++)

        u = Read (), v = Read (), Add_Edge (u, v);

    Tree_Dp (1, -1);

    // for (int i = 1; i <= n; i++)

    //     printf ("%lld %lld %lld %lld\n", Dp[i][0], Dp[i][1], Dp[i][2], Dp[i][3]);

    Print (Dp[1][0], '\n');

    return 0;

}

「CF1120D」Power Tree

将所有叶子按 DFS 序拉成一个序列，记点 \(u\) 子树内最靠左的叶子为 \(l_u\)，最靠右的叶子为 \(r_u\)。不难发现，题目中一次操作等价于在 \([l_u, r_u]\) 上做区间修改，也可转换为在差分序列上单点修改。

即是说对于点 \(u\)，我们可以将 \(l_u\) 处加上 \(d\)，在 \(r_u + 1\) 处减去 \(d\)，目标是使所有点都为 \(0\)。

如果将 \(l_u\) 和 \(r_u + 1\) 进行连边，边权为 \(w_u\)。如果原树上所有节点的对应点都可以跑到新节点 \(n + 1\) 上，则一定可以得到符合题意的最终状态（逆向树上差分？

题目转换为求哪些点可能出现在无向图最小生成树上，Kruskal 判一下即可。

出现了！写并查集不写路径压缩的大憨憨！

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

typedef long long LL;

int Abs (int x) { return x < 0 ? -x : x; }

int Max (int x, int y) { return x > y ? x : y; }

int Min (int x, int y) { return x < y ? x : y; }

int Read () {

    int x = 0, k = 1;

    char s = getchar ();

    while (s < '0' || s > '9') {

        if (s == '-')

            k = -1;

        s = getchar ();

    }

    while ('0' <= s && s <= '9')

        x = (x << 3) + (x << 1) + (s ^ 48), s = getchar ();

    return x * k;

}

void Write (LL x) {

    if (x < 0)

        putchar ('-'), x = -x;

    if (x > 9)

        Write (x / 10);

    putchar (x % 10 + '0');

}

void Print (LL x, char s) { Write (x), putchar (s); }

const int Inf = 1e9;

const int Maxn = 2e5 + 5;

struct Node {

    int l, r;

    Node () {}

    Node (int L, int R) { l = L, r = R; }

} q[Maxn];

struct Edge {

    int u, v, w, Pos;

    Edge () {}

    Edge (int U, int V, int W, int P) { u = U, v = V, w = W, Pos = P; }

    friend bool operator < (Edge x, Edge y) { return x.w < y.w; }

} e[Maxn];

bool Vis[Maxn];

vector <int> Graph[Maxn];

int w[Maxn], Dfn[Maxn], Fa[Maxn], Cnt;

void Add_Edge (int u, int v) { Graph[u].push_back (v), Graph[v].push_back (u); }

void Make_Tree (int n) {

    for (int i = 1; i <= n; i++)

        Fa[i] = i;

}

int Find_Set (int x) { return Fa[x] == x ? x : Fa[x] = Find_Set (Fa[x]); }

void Dfs (int u, int Fa) {

    q[u].l = Inf, q[u].r = -Inf;

    for (int i = 0, v; i < Graph[u].size (); i++) {

        v = Graph[u][i];

        if (v == Fa)

            continue;

        Dfs (v, u), q[u].l = Min (q[u].l, q[v].l), q[u].r = Max (q[u].r, q[v].r);

    }

    if (Graph[u].size () == 1 && u != 1)

        q[u].l = q[u].r = ++Cnt;

    e[u] = Edge (q[u].l, q[u].r + 1, w[u], u);

}

int main () {

    int n = Read ();

    for (int i = 1; i <= n; i++)

        w[i] = Read ();

    for (int i = 1, u, v; i < n; i++)

        u = Read (), v = Read (), Add_Edge (u, v);

    Dfs (1, -1), sort (e + 1, e + n + 1);

    Make_Tree (Cnt + 1), Cnt++;

    LL Res = 0;

    int Tot = 0;

    for (int l = 1, r; l <= n; l = r + 1) {

        r = l;

        while (r + 1 <= n && e[r].w == e[r + 1].w)

            r++;

        for (int i = l, u, v; i <= r; i++) {

            u = Find_Set (e[i].u), v = Find_Set (e[i].v);

            if (u != v)

                Vis[e[i].Pos] = true, Tot++;

        }

        for (int i = l, u, v; i <= r; i++) {

            u = Find_Set (e[i].u), v = Find_Set (e[i].v);

            if (u != v)

                Fa[v] = u, Res += e[i].w;

        }

    }

    Print (Res, ' '), Print (Tot, '\n');

    for (int i = 1; i <= n; i++)

        if (Vis[i])

            Print (i, ' ');

    putchar ('\n');

    return 0;

}

最新文章

  1. session、cookie浅见
  2. 让浏览器不再显示 https 页面中的 http 请求警报
  3. guava学习--Function、Predicate
  4. 数据表格datagrid内容整理
  5. react-native SyntaxError xxxxx/xx.js:Unexpected token (23:24)
  6. Moebius集群:SQL Server一站式数据平台
  7. 横屏EditText问题
  8. Python函数,参数,变量
  9. SULogger：iOS日志可视化工具
  10. ☀【Grunt】no such file or directory, imagemin
  11. jsonp Ajax跨域请求
  12. CSDN专家吐槽实录
  13. JavaScript实现全选和全不选
  14. C#编程语言之委托与事件（一）—— C/C++函数指针和C#委托初步
  15. linux 下修改etc/profile文件
  16. collections.deque
  17. 转 C#实现PID控制的模拟测试和曲线绘图
  18. pandas DataFrame(4)-向量化运算
  19. windows 网卡配置的设置命令
  20. 洛谷P3248 [HNOI2016]树(主席树 倍增 )

热门文章

  1. [Istio是什么？] 还不知道你就out了,一文40分钟快速理解
  2. Citus 11(分布式 PostgreSQL) 文档贡献与本地运行
  3. 优化 Docker 镜像大小常见方法
  4. 流量录制回放工具jvm-sandbox-repeater入门篇——录制和回放
  5. 函数式接口和@FunctionalInterface
  6. 软件开发架构，网络编程简介，OSI七层协议，TCP和UDP协议
  7. Java 16 新特性：record类
  8. 前后端分离，SpringBoot如何实现验证码操作
  9. @ConfigurationProperties(prefix = &quot;server-options&quot;) 抛出 SpringBoot Configuration Annotation Processor not configured 错误
  10. 镜头随人物而动，视频编辑服务让用户稳站C位