3751. 卡车送货

有空再写题解

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;

class Road{
public:
    int X, Y, L;
    LL A;
};

class Query{
public: 
    int C, W;
    LL ans;
};

class Data {
public:     
    Data(int t, int i, int v) : type(t), index(i), value(v) {}
    int type; 
    int index;
    int value;
    bool operator<(const Data& another) const {
        if(value != another.value) {
            return value < another.value;
        }
        return type < another.type;
    }
};

const int N = 50010, M = 100010;
Road road[N];
Query query[M];
vector<int> g[N];
int bpos[N], epos[N], p[N];

LL gcd(LL a, LL b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}

struct Node
{
    int l, r, lazy;
    LL val;
}tr[N * 4];

void pushdown(int u)
{
    if(tr[u].lazy) {
        int lc = u << 1, rc = u << 1 | 1;
        tr[lc].val = gcd(tr[u].val, tr[lc].val);
        tr[rc].val = gcd(tr[u].val, tr[rc].val);
        tr[u].lazy = 0, tr[lc].lazy = 1, tr[rc].lazy = 1;
    }
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, 0};
    else
    {
        tr[u] = {l, r, 0, 0};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}


void update(int u, int l, int r, long long d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].val = gcd(tr[u].val, d);
        tr[u].lazy = 1;
        return;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
    }
}

LL query_seg(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    { 
        return tr[u].val;  // TODO 需要补充返回值
    }
    else
    {
        LL res = 0;
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid ) res =  query_seg(u << 1, l, r);
        if (l > mid) res = query_seg(u << 1 | 1, l, r);
        return res;
    }
}


void dfs(int u, int fa, int &counter) {
    bpos[u] = ++counter;
    p[u] = fa;
    for(int i=0; i<g[u].size(); i++)  {
        int ne = g[u][i];
        if(ne == fa) continue;
        dfs(ne, u, counter);
    }
    epos[u] = counter;
}

void solve(int test_case) 
{
    int n, Q;
    scanf("%d%d", &n, &Q);
    for(int i=1; i<=n; i++) g[i].clear();
    vector<Data> v;
    for(int i=1; i<n; i++) {
        scanf("%d%d%d%lld", &road[i].X, &road[i].Y, &road[i].L, &road[i].A);
        g[road[i].X].push_back(road[i].Y);
        g[road[i].Y].push_back(road[i].X);
        v.emplace_back(0, i, road[i].L); // limit
    }

    for(int i=0; i<Q; i++) {
        scanf("%d%d", &query[i].C, &query[i].W);
        v.emplace_back(1, i, query[i].W); // weight
    }

    sort(v.begin(), v.end());

    int counter = 0;
    dfs(1, -1, counter);
    build(1, 1, N);

    for(int i=0; i<(int)v.size(); i++) {
        if(v[i].type == 0) {
            int X = road[v[i].index].X;
            int Y = road[v[i].index].Y;
            LL A = road[v[i].index].A;
            if(p[X] == Y) swap(X, Y);
            update(1, bpos[Y], epos[Y], A);
        } else {
            int C = query[v[i].index].C;
            query[v[i].index].ans = query_seg(1, bpos[C], bpos[C]);
        }
    }

    cout << "Case #" << test_case << ": ";
    for(int i=0; i<Q; i++) {
        cout << query[i].ans << ' ';
    }
    cout << endl;
}

int main()
{
    int T;
    scanf("%d", &T);
    for(int i=1; i<=T; i++) solve(i);
    return 0;
}