2019牛客暑期NOIP真题班提高组6-树

1. 联合权值

来源：NOIP2014提高组 https://ac.nowcoder.com/acm/contest/262/E

算法知识点: DFS，树的深度优先遍历

复杂度： $O(N)$

解题思路：

距离为2的点对有两种：八字形和1字形。

对于八字形：直接将当前节点的所有子节点两两配对的结果统计出来即可。这一步线性扫描一遍即可，不需要 $O(N^2)$ 枚举。
我们以求总和为例，求最大值类似。从前往后枚举子节点时维护变量 $sum$ ，表示前面所有子节点的权值和，则每次将 $sum$ 与当前节点的权值的乘积累加起来，就是当前节点的所有子节点两两配对的总权值和。

对于1字形，我们在DFS过程中对每个点维护两个值：f[u]表示节点u的所有子节点权值的最大值，g[u]表示节点u的所有子节点权值之和。那么以u为最高点的1字形点对权值之和就是u的权值乘以u的所有子节点的g[s]之和。求最大值类似。

由于题目中要求的是有序点对的和，因此权值和需要乘2。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 200010,
    M = N * 2,
    mod = 10007;

int n;
int h[N], e[M], ne[M], idx;
int w[N];
int ans_max, ans_sum;
int f[N], g[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int father)
{
    int sum = 0, maxv = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != father)
        {
            dfs(j, u);
            ans_max = max(ans_max, w[u] *f[j]);
            ans_max = max(ans_max, maxv *w[j]);
            maxv = max(maxv, w[j]);
            ans_sum = (ans_sum + w[u] *g[j]) % mod;
            ans_sum = (ans_sum + sum *w[j]) % mod;
            sum = (sum + w[j]) % mod;
            f[u] = max(f[u], w[j]);
            g[u] = (g[u] + w[j]) % mod;
        }
    }
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);

    dfs(1, -1);
    printf("%d %d\n", ans_max, ans_sum * 2 % mod);

    return 0;
}

2. 树网的核

来源：NOIP2007提高组 https://ac.nowcoder.com/acm/contest/255/D

算法知识点: 二分，树的直径，贪心，树的遍历

复杂度： $O(NlogS)$

解题思路：

二分最小偏心距，判断在直径上是否存在一段长度不超过 $s$ 的路径，使得其余所有点到路径的距离小于等于枚举的值。
接下来在直径上找到与 u 的距离不超过 mid 的前提下，距离u最远的节点，作为节点 p。类似地，在直径上找到与 v 的距离不超过 mid 的前提下，距离 v 最远的节点，作为节点 q。

根据直径的最长性，任何从 u, p 之间分叉离开直径的子树，其最远点与 p 的距离都不会比 u 更远。所以 p, q就是在满足直径两侧的那部分节点偏心距不超过 mid 的前提下，尽量靠近树网中心的节点。

接下来判断 p, q 之间的距离是否不超过 s，以及p, q之间的所有点到其他所有点的最短距离是否不超过mid即可。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long LL;
typedef pair <int, int> PII; const int N = 500010,
    M = N * 2;

int n, s;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N], pre[N];
vector<PII> path;
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void bfs(int start)
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    memset(pre, -1, sizeof pre);
    dist[start] = 0;
    q[0] = start;

    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                pre[j] = t;
                dist[j] = dist[t] + w[i];
                q[++tt] = j;
            }
        }
    }
}

int bfs_max_dist(int start)
{
    int res = 0;
    int hh = 0, tt = 0;
    q[0] = start;
    while (hh <= tt)
    {
        int t = q[hh++];
        res = max(res, dist[t]);

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                st[j] = true;
                dist[j] = dist[t] + w[i];
                q[++tt] = j;
            }
        }
    }
    return res;
}

int get_max()
{
    int t = 1;
    for (int i = 1; i <= n; i++)
        if (dist[t] < dist[i])
            t = i;
    return t;
}

bool check(int mid)
{
    int u = 0, v = path.size() - 1;
    while (u + 1 < path.size() && path[u + 1].second <= mid) u++;
    while (v - 1 >= 0 && path.back().second - path[v - 1].second <= mid) v--;
    if (u > v) return true;
    if (path[v].second - path[u].second > s) return false;

    memset(st, false, sizeof st);
    memset(dist, 0, sizeof dist);
    for (auto p: path) st[p.first] = true;

    for (int i = u; i <= v; i++)
        if (bfs_max_dist(path[i].first) > mid)
            return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &s);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    bfs(1);
    int u = get_max();
    bfs(u);
    int v = get_max();
    while (v != -1)
    {
        path.push_back(
        {
            v, dist[v]
        });
        v = pre[v];
    }
    reverse(path.begin(), path.end());

    int l = 0, r = 2e9;
    while (l < r)
    {
        int mid = (LL) l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}

3. 运输计划

来源：NOIP2015提高组 https://ac.nowcoder.com/acm/contest/263/C

算法知识点: LCA，树上差分，二分

复杂度： $O((N+M)logT)$

解题思路：

二分时间，则原问题变成一个判定性问题：是否可以通过去掉一条边，使所有路径的总长度在 $t$ 以内。

此时去掉所有长度大于 $t$ 的路径的最长公共边一定是最优的。

那怎么找出所有公共边呢？我们可以将每条路径上的所有边加1，最后判断每条边上的总和是否等于路径总数即可。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef pair <int, int> PII; const int N = 300010,
    M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], depth[N];
int f[N][20], seq[N], cnt;
int sum[N];
PII trans[N];
int blca[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int dep, int father)
{
    cnt++;
    seq[cnt] = u;
    depth[u] = dep;

    for (int i = 1; i < 20; i++) f[u][i] = f[f[u][i - 1]][i - 1];

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != father)
        {
            dist[j] = dist[u] + w[i];
            f[j][0] = u;
            dfs(j, dep + 1, u);
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    int d = depth[x] - depth[y];
    for (int i = 0; i < 20; i++)
        if (d >> i &1)
            x = f[x][i];
    if (x == y) return x;

    for (int i = 19; i >= 0; i--)
        if (f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    return f[x][0];
}

bool check(int mid)
{
    memset(sum, 0, sizeof sum);
    int maxd = 0, s = 0;
    for (int i = 1; i <= m; i++)
    {
        int x = trans[i].first, y = trans[i].second;
        int p = blca[i];
        int d = dist[x] + dist[y] - dist[p] * 2;
        if (d > mid)
        {
            sum[x] += 1, sum[y] += 1;
            sum[p] -= 2;
            maxd = max(maxd, d - mid);
            s++;
        }
    }

    if (!s) return true;

    for (int i = n; i; i--)
    {
        int x = seq[i];
        sum[f[x][0]] += sum[x];
    }
    for (int i = 1; i <= n; i++)
        if (sum[i] == s && dist[i] - dist[f[i][0]] >= maxd)
            return true;
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    dfs(1, 0, -1);

    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        trans[i] = {
            x, y
        };
        blca[i] = lca(x, y);
    }

    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);
    return 0;
}

4. 旅行

来源：NOIP2018提高组 https://ac.nowcoder.com/acm/contest/294/D

算法知识点: 树的深度优先遍历，DFS，基环树

复杂度： $O(N^2)$

解题思路：

如果是一棵树，则我们一定从1号点开始遍历，每次按编号从小到大的顺序遍历所有子节点，得到的DFS序列的字典序最小。

这道题目给定的树还有可能是基环树，即树中有一个环。
此时可以发现：不论如何遍历，我们一定只会遍历其中 $n-1$ 条边，因此可以枚举删掉哪条边，然后再用在树中遍历的方式求出最小字典序即可。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair <int, int> PII; const int N = 5010;

int n, m;
vector<int> e[N];
PII edge[N];
int del_u, del_v;
vector<int> ans(N, N);
vector<int> path(N);
bool st[N];
int cnt, state;

bool dfs(int u)
{
    if (!state)
    {
        if (u > ans[cnt]) return true;
        if (u < ans[cnt]) state = -1;
    }

    st[u] = true;
    path[cnt++] = u;

    for (int i = 0; i < e[u].size(); i++)
    {
        int x = e[u][i];
        if (!(x == del_u && u == del_v) && !(x == del_v && u == del_u) && !st[x])
            if (dfs(x)) return true;
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
        edge[i] = {
            a, b
        };
    }

    for (int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end());
    if (n == m)
    {
        for (int i = 0; i < m; i++)
        {
            del_u = edge[i].first, del_v = edge[i].second;

            memset(st, false, sizeof st);
            cnt = state = 0;
            dfs(1);
            if (cnt == n) ans = path;
        }
    }
    else
    {
        dfs(1);
        if (cnt == n) ans = path;
    }
    for (int i = 0; i < n; i++) printf("%d ", ans[i]);

    return 0;
}

另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ