牛客网-2018 美团 CodeM 编程大赛-初赛 A 轮-3-城市漫游

ACM模版

描述

题解

这个题出的十分好，让我回忆起了遗忘已久的一些东西。

首先，题意是给定一个树， n n 个结点， n−1 $n-1$ 条边，每条边有时间花费 zi z i ，给定若干组起点 S S 和 T $T$，要求从 S S 到 T $T$ 时，必须每条边都经过至少 li l i 次，问最少花费。

这里，我们首先很容易想到的是应该和 S S 到 T $T$ 的最短路径（这里的最短路径不考虑边的重复次数）有关，并且题意中说到 min(li)>0 m i n ( l i ) > 0 ，也就是数据保证每条边都必须经过一次，所以我们可以将所有边分为两种，一种是在最短路径上的，一种是不在最短路径上的。对于前者，如果他在最短路径上，我们很容易实现每条边经过恰好 li l i 次；而对于后者，则不能，因为我们在离开最短路径去其他路径上时必须重新返回到最短路径上，所以对于这些不在最短路径上的边时，我们必然经过偶数次，那么当 li%2==0 l i % 2 == 0 时，没有什么疑问，那就是经过 li l i 次，而当 li%2==1 l i % 2 == 1 时，我们需要经过它 li+1 l i + 1 次才行。

说到这里，其实已经很简单了，只剩下一个问题，就是如何求 S S 到 T $T$ 最短路径的长度，因为这是一棵树，所以最短路径唯一，我们可以通过 LCA L C A 来求，公式为 S S 到根的距离加上 T $T$ 到根的距离减去二倍的 LCA(S,T) L C A ( S , T ) 到根的距离。

此时，两个部分的全部考虑完毕，已经能够完美 AC A C 了，不过这里有一个小小的技巧，我们可以首先将所有的路径都考虑为不在最短路径上，所以都考虑为偶数次，然后建树时，将所有 li%2==1 l i % 2 == 1 的路径的花费置为 −costi − c o s t i ，这样再去求最短路径上的代价，相加即可，完美抵消最短路径上多走的那些路。

这里稍微扩展一下，如果某些路径的花费是可变的，那么在根据公式求最短路径上的花费时，就要用到树链剖分 + + 树状数组了。

这里我的代码写的略微复杂了，原本只需要 LCA $LCA$ 算法即可， 这里我用到了树链剖分和树状数组，多此一举了，完全没有必要，因为这个题路径的花费是不可变的（在以前代码上改的代码，所以懒得修改了）。

代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

#define lson rt << 1
#define rson lson | 1

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

struct node
{
    int id;
    int to;
    ll cost;
} Q;

struct nn
{
    int l, r, mn;
} PP[MAXN << 4];

int n, cnt;
int x[MAXN], y[MAXN];
int wx[MAXN][2];
int pre[MAXN << 2];
int front_edge[MAXN][2];
ll z[MAXN], tree[MAXN << 2];
bool vis[MAXN << 1];
vector<node> vn[MAXN];

void add_edge(int x_, int y_, ll z_, int id)
{
    Q.cost = z_;
    Q.id = id;
    Q.to = y_;
    vn[x_].push_back(Q);
    Q.to = x_;
    vn[y_].push_back(Q);
}

int lowit(int x)
{
    return x & (-x);
}

void add(int a, ll b)
{
    for (; a <= n; a += lowit(a))
    {
        tree[a] += b;
    }
}

ll query(int rt)
{
    ll ans = 0;
    for (; rt; rt -= lowit(rt))
    {
        ans += tree[rt];
        ans %= MOD;
    }

    return ans;
}

void create(int l, int r, int rt)
{
    PP[rt].l = l;
    PP[rt].r = r;

    if (l == r)
    {
        PP[rt].mn = wx[pre[l]][0];
        return ;
    }

    int m = (l + r) >> 1;
    create(l, m, lson);
    create(m + 1, r, rson);
    PP[rt].mn = min(PP[lson].mn, PP[rson].mn);
}

int LCA(int l, int r, int rt)
{
    if (l == PP[rt].l && r == PP[rt].r)
    {
        return PP[rt].mn;
    }

    int m = (PP[rt].l + PP[rt].r) >> 1;
    if (l > m)
    {
        return LCA(l, r, rson);
    }
    else if (r <= m)
    {
        return LCA(l, r, lson);
    }
    else
    {
        return min(LCA(l, m, lson), LCA(m + 1, r, rson));
    }
}

void dfs(int rt)
{
    vis[rt] = false;
    wx[rt][0] = ++cnt;
    pre[cnt] = rt;

    for (int i = 0; i < vn[rt].size(); i++)
    {
        if (vis[vn[rt][i].to])
        {
            front_edge[vn[rt][i].id][0] = cnt;
            add(cnt, vn[rt][i].cost);

            dfs(vn[rt][i].to);

            front_edge[vn[rt][i].id][1] = cnt;
            add(cnt, -vn[rt][i].cost);
            wx[rt][1] = ++cnt;
            pre[cnt] = rt;
        }
    }

    wx[rt][1] = cnt;
    pre[cnt] = rt;
}

ll m;

int main()
{
    scanf("%d", &n);

    ll sum = 0, l;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d%lld%lld", &x[i], &y[i], &z[i], &l);

        // 先每条边跑偶数次，且保证至少 l 次
        if (l % 2 == 0)
        {
            sum += z[i] * l;
            sum %= MOD;
            l = 1;
        }
        else
        {
            sum += z[i] * (l + 1);
            sum %= MOD;
            l = -1;
        }
        z[i] *= l;                      // 对于奇数的情况多跑了一次

        add_edge(x[i], y[i], z[i], i);  // 初始建树
    }

    int S, T, tmp;
    scanf("%lld", &m);
    // n == 1 时结果均为 0
    if (n == 1)
    {
        while (m--)
        {
            scanf("%d%d", &S, &T);
            printf("0\n");
        }

        return 0;
    }

    memset(vis, true, sizeof(vis));
    memset(tree, 0, sizeof(tree));
    n = 2 * n - 2;
    cnt = 0;

    dfs(1);
    create(1, n, 1);

    while (m--)
    {
        scanf("%d%d", &S, &T);

        S = wx[S][0];
        T = wx[T][0];
        if (S < T)
        {
            tmp = LCA(S, T, 1);
        }
        else
        {
            tmp = LCA(T, S, 1);
        }

        ll ans = query(S - 1) - 2 * query(tmp - 1) + query(T - 1);
        ans += sum;
        ans %= MOD;
        ans += MOD;
        ans %= MOD;
        printf("%lld\n", ans);
    }

    return 0;
}