题解：P10773 [NOISG2021 qualification] Truck

题目链接

• 洛谷 P10773 [NOISG2021 qualification] Truck

解题思路

首先，我们注意到可以把运输的过程反过来，从 $y$ 点开始，运送的价值初始值为 $G$，每走过一条边就产生一次代价，并将运送的价值加上这条边的 $T$。

于是我们得到如下结论：

若有三个点 $x,y,z$ 满足 $y$ 在从 $x$ 到 $z$ 的简单路径上，

令 $val_{a,b}$ 为从点 $a$ 到点 $b$ 的代价， $sumt_{a,b}$ 为从点 $a$ 到点 $b$ 的边权 $T$ 之和，$sumd_{a,b}$ 为从点 $a$ 到点 $b$ 的边权 $D$ 之和。

则有：

$$val_{x,z}=val_{x,y}+val_{y,z}+sumt_{x,y} \times sumd_{y,z}$$

于是我们就可以用树链剖分加线段树维护答案。

参考代码（内附注释）

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200005 , mod = 1000000007;
int n , G , Q;
int son[N] , dep[N] , siz[N] , fa[N] , top[N] , dfn[N] , pos[N] , tot;//树剖要用的数组
int beft[N] , befd[N];//化边为点

struct edge
{
    int to , D , T;//存边
};
vector <edge> g[N];

struct seg
{
    int sumd , sumt , up , down;//sumd和sumt含义如上，up表示在这个区间内从下往上走的代价，down表示在这个区间内从上往下走的代价
};
seg s[N << 1] , null;//null表示一个空点

seg operator +(seg x , seg y)
{
    seg res;
    res.down = (x.down + y.down + (x.sumt * y.sumd) % mod) % mod;
    res.up = (x.up + y.up + (x.sumd * y.sumt) % mod) % mod;
    res.sumd = (x.sumd + y.sumd) % mod;
    res.sumt = (x.sumt + y.sumt) % mod;
    return res;
}//将区间合并重载为加法

void dfs1(int u , int pre)//建树+预处理 
{
    fa[u] = pre;
    if(u == 1)
    {
        fa[u] = u;
    }
    siz[u] = 1;
    dep[u] = dep[pre] + 1;
    for(auto [v , d , t] : g[u])
    {
        if(v == pre)
        {
            continue;
        }
        befd[v] = d;
        beft[v] = t;
        dfs1(v , u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]])
        {
            son[u] = v;
        }
    }
}

void dfs2(int u , int pre)//树剖
{
    dfn[u] = ++tot;
    pos[tot] = u;
    if(!son[u])
    {
        return;
    }
    top[son[u]] = top[u];
    dfs2(son[u] , u);
    for(auto [v , d , t] : g[u])
    {
        if(v == pre || v == son[u])
        {
            continue;
        }
        top[v] = v;
        dfs2(v , u);
    }
}

void build(int num , int l , int r)//建线段树
{
    if(l == r)
    {
        s[num].sumd = befd[pos[l]];
        s[num].sumt = beft[pos[r]];
        return;
    }
    int mid = (l + r) >> 1;
    build(num << 1 , l , mid);
    build(num << 1 | 1 , mid + 1 , r);
    s[num] = s[num << 1] + s[num << 1 | 1];
}

void update(int num , int l , int r , int x , int val)//更新点权
{
    if(l > x || r < x)
    {
        return;
    }
    if(l == x && r == x)
    {
        s[num].sumt = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(num << 1 , l , mid , x , val);
    update(num << 1 | 1 , mid + 1 , r , x , val);
    s[num] = s[num << 1] + s[num << 1 | 1];
}

void change(int x , int y , int t)//更改操作
{
    if(dep[x] > dep[y])
    {
        swap(x , y);
    }
    update(1 , 1 , n , dfn[y] , t);
}

seg get(int num , int l , int r , int x , int y)//线段树上区间查找 
{
    if(l > y || r < x)
    {
        return null;
    }
    if(l >= x && r <= y)
    {
        return s[num];
    }
    int mid = (l + r) >> 1;
    return get(num << 1 , l , mid , x , y) + get(num << 1 | 1 , mid + 1 , r , x , y);
}

int query(int x , int y)//查询操作
{
    int res1 = 0 , nowt = 0 , res2 = 0 , nowd = 0 , totd = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] >= dep[top[y]])
        {
            seg awa = get(1 , 1 , n , dfn[top[x]] , dfn[x]);
            totd = (totd + awa.sumd) % mod;
            res1 = (res1 + (nowt * awa.sumd) % mod + awa.up) % mod;
            nowt = (nowt + awa.sumt) % mod;
            x = fa[top[x]];
        }
        else
        {
            seg awa = get(1 , 1 , n , dfn[top[y]] , dfn[y]);
            totd = (totd + awa.sumd) % mod;
            res2 = (res2 + (nowd * awa.sumt) % mod + awa.down) % mod;
            nowd = (nowd + awa.sumd) % mod;
            y = fa[top[y]];
        }
    }
    if(x != y)
    {
        if(dep[x] >= dep[y])
        {
            seg awa = get(1 , 1 , n , dfn[y] + 1 , dfn[x]);
            totd = (totd + awa.sumd) % mod;
            res1 = (res1 + (nowt * awa.sumd) % mod + awa.up) % mod;
            nowt = (nowt + awa.sumt) % mod;
        }
        else
        {
            seg awa = get(1 , 1 , n , dfn[x] + 1 , dfn[y]);
            totd = (totd + awa.sumd) % mod;
            res2 = (res2 + (nowd * awa.sumt) % mod + awa.down) % mod;
            nowd = (nowd + awa.sumd) % mod;
        }
    }
    res1 = (res1 + (nowt * nowd) % mod + res2) % mod;
    return (res1 + (G * totd) % mod) % mod;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    null.down = 0;
    null.sumd = 0;
    null.sumt = 0;
    null.up = 0;//初始化
    cin >> n >> G;
    for(int i = 1 , a , b , D , T ; i < n ; i++)
    {
        cin >> a >> b;
        edge e;
        e.to = b;
        cin >> e.D >> e.T;
        g[a].push_back(e);
        e.to = a;
        g[b].push_back(e);
    }
    dfs1(1 , 0);
    top[1] = 1;
    dfs2(1 , 0);
    build(1 , 1 , n);//预处理
    cin >> Q;
    int op , x , y , t;
    while(Q--)
    {
        cin >> op >> x >> y;
        if(op)
        {
            cout << query(y , x) << endl;//处理询问
        }
        else
        {
            cin >> t;
            change(x , y , t);//处理更改
        }
    }
    return 0;
}

附：谴责搬题人

充满了血泪的控诉，详情请看原帖。