题解 P3241 【[HNOI2015]开店】

· · 题解

建议先做一下：P4211 [LNOI2014]LCA

如果你做了上面那题，你会发现此题为强制在线版，而且添加了边权。

其实不要紧，那个询问差分的思路仍然可以继续使用，只不过要用可持久化线段树实现。

我们可以先把 age 排序，然后先树剖，按 age 顺序建主席树。

我们发现，有边权之后有些难处理。

首先是主席树要标记永久化，因为每次修改是标记翻倍，所以可以维护 tim 数组，表示覆盖几次，可以乘上边权和来计算贡献。

其次就是要利用距离公式来计算答案，如询问l r x那么答案应为： dis[x] * (r - l + 1) + (sumd[r] - sumd[l - 1]) - Query(root[r], root[l - 1], x) * 2)

code:

// Program written by Liu Zhaozhou ~~~

const int Maxn = 15e4 + 1;
const int Maxm = 3e5 + 1;
const int Maxt = Maxn * 49;

int n, q, ages, cnt = 0, head[Maxn], ver[Maxm], edge[Maxm], nxt[Maxm];
inline void AddEdge(int u, int v, int w) {
    ver[++cnt] = v, edge[cnt] = w, nxt[cnt] = head[u], head[u] = cnt;
    ver[++cnt] = u, edge[cnt] = w, nxt[cnt] = head[v], head[v] = cnt;
}

struct state {
    int age, idx;
    state(void) { age = idx = 0; }
    state(int a, int i) : age(a), idx(i) {}
    inline bool operator < (const state&rhs) const { return age == rhs.age ? idx < rhs.idx : age < rhs.age; } 
} a[Maxn];

ll dis[Maxn], sume[Maxn], sumd[Maxn];
int sze[Maxn], son[Maxn], fat[Maxn];
int top[Maxn], dfn[Maxn], timer = 0;
inline void DfsFir(int u) {
    sze[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        if (ver[i] == fat[u]) continue;
        dis[ver[i]] = dis[u] + edge[i];
        fat[ver[i]] = u; DfsFir(ver[i]);
        sze[u] += sze[ver[i]];
        if (sze[son[u]] < sze[ver[i]]) son[u] = ver[i];
    }
}

inline void DfsSec(int u, int t) {
    top[u] = t, dfn[u] = ++timer;
    sume[timer] = dis[u] - dis[fat[u]];
    if (son[u]) DfsSec(son[u], t);
    for (int i = head[u]; i; i = nxt[i]) {
        if (ver[i] == fat[u] || ver[i] == son[u]) continue;
        DfsSec(ver[i], ver[i]);
    }
}

int lson[Maxt], rson[Maxt], tim[Maxt], root[Maxn], tot = 0; ll sum[Maxt];
inline void inherit(int p, int q) { lson[p] = lson[q], rson[p] = rson[q], sum[p] = sum[q], tim[p] = tim[q]; }
inline void insert(int &pos, int l, int r, int L, int R) {
    inherit(++tot, pos); pos = tot; 
    if (L <= l && R >= r) { sum[pos] += sume[r] - sume[l - 1]; ++tim[pos]; return; }
    int mid = l + r >> 1;
    if (L <= mid) insert(lson[pos], l, mid, L, R);
    if (R > mid) insert(rson[pos], mid + 1, r, L, R);
    sum[pos] = sum[lson[pos]] + sum[rson[pos]] + (sume[r] - sume[l - 1]) * tim[pos];
}

inline void Modify(int &rt, int pos) { while (pos) insert(rt, 1, n, dfn[top[pos]], dfn[pos]), pos = fat[top[pos]]; }
inline ll query(int p, int q, int l, int r, int L, int R) {
    if (!p) return 0;
    if (L <= l && R >= r) return sum[p] - sum[q];
    int mid = l + r >> 1; ll ret = (sume[min(R, r)] - sume[max(L, l) - 1]) * (tim[p] - tim[q]);
    if (L <= mid) ret += query(lson[p], lson[q], l, mid, L, R);
    if (R > mid) ret += query(rson[p], rson[q], mid + 1, r, L, R);
    return ret;
}

inline ll Query(int p, int q, int x) { ll ret = 0ll; while (x) ret += query(p, q, 1, n, dfn[top[x]], dfn[x]), x = fat[top[x]]; return ret; }

signed main(void) {
//  file("");
    read(n), read(q), read(ages);
    for (int i = 1; i <= n; i++) read(a[i].age), a[i].idx = i;
    sort(a + 1, a + n + 1);
    for (int i = 1, u, v, w; i < n; i++) read(u), read(v), read(w), AddEdge(u, v, w);
    DfsFir(1), DfsSec(1, 1);
    for (int i = 1; i <= n; i++) sume[i] += sume[i - 1], sumd[i] = sumd[i - 1] + dis[a[i].idx];
    for (int i = 1; i <= n; i++) Modify(root[i] = root[i - 1], a[i].idx);
    ll lastans = 0; int l, r, x;
    while (q--) {
        read(x), read(l), read(r);
        l = (l + lastans) % ages;
        r = (r + lastans) % ages;
        if (l > r) swap(l, r);
        l = lower_bound(a + 1, a + n + 1, state(l, 0)) - a;
        r = upper_bound(a + 1, a + n + 1, state(r, n)) - (a + 1);
        writeln(lastans = (dis[x] * (r - l + 1) + (sumd[r] - sumd[l - 1]) - Query(root[r], root[l - 1], x) * 2));
    }
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/