头像

Crescent




离线:1天前


最近来访(13)
用户头像
KS阿杰
用户头像
随便_80
用户头像
赤旗
用户头像
zombotany
用户头像
王小强
用户头像
千山
用户头像
zeda
用户头像
endinggy
用户头像
海绵宝宝嘉然儿
用户头像
凌乱之风
用户头像
lyktes
用户头像
妖娆
用户头像
Gtwff

分享 图论笔记

1.P5905 【模板】Johnson 全源最短路

 const int N = 3e3 + 10, M = 2e4 + 10, INF = 1e9;

int n, m, dist[N], h[N], e[M], ne[M], w[M], idx, G[N], cnt[N];
int q[N];

bool st[N];

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

bool spfa(int dist[]) {
    for (int i = 1; i <= n; i ++ ) dist[i] = INF;
    int hh = 0, tt = 0;
    q[tt ++ ] = 0; dist[0] = 0, st[0] = 1;
    while (hh != tt) {
        int u = q[hh ++ ];
        if (hh == N) hh = 0;
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (chkmin(dist[j], dist[u] + w[i])) {
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= n + 1) return true;
                if (!st[j]) {
                    q[tt ++ ] = j;
                    st[j] = true;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return false;
}

priority_queue<pi, vector<pi>, greater<pi>> Q;

void dijkstra(int S) {
    for (int i = 1; i <= n; i ++ ) dist[i] = INF, st[i] = 0;
    dist[S] = 0;
    Q.push({0, S});
    while (Q.size()) {
        auto t = Q.top();
        Q.pop();
        if (st[t.se]) continue;
        st[t.se] = true;
        for (int i = h[t.se]; ~i; i = ne[i]) {
            int j = e[i];
            if (chkmin(dist[j], t.fi + w[i])) {
                if (!st[j]) {
                    Q.push({dist[j], j});
                }
            }
        }
    }
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c);
    }
    for (int i = 1; i <= n; i ++ ) add(0, i, 0);
    if (spfa(G)) {
        puts("-1"); 
    } else {
        for (int u = 1; u <= n; u ++ )
            for (int i = h[u]; ~i; i = ne[i]) {
                int j = e[i];
                w[i] += G[u] - G[j];
            }
        for (int i = 1; i <= n; i ++ ) {
            dijkstra(i);
            LL res = 0;
            for (int j = 1; j <= n; j ++ ) {
                int dis = dist[j];
                if (i != j && dist[j] != INF) dis -= G[i] - G[j];
                res += 1ll * dis * j;
            }
            cout << res << '\n';
        }
    }
    return 0;
}


活动打卡代码 AcWing 2226. 开店

Crescent
19天前
// Problem: 开店
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/2228/
// Memory Limit: 256 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1.5e5 + 10, M = N << 1, Q = 2e5 + 10;

int n, m, h[N], e[M], ne[M], w[M], K, idx, age[N];
bool st[N];

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

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

struct Son {
    int age;
    LL dist;
    bool inline operator< (const Son &b) const {
        return age < b.age;
    }
};
vector<Son> son[N][3];
struct Fa {
    int wc, id;
    LL dist;
};
vector<Fa> f[N];
void get_dist(int u, int fa, int k, LL dist, int &wc, vector<Son> &p) {
    if (st[u]) return ;
    p.pb({age[u], dist});
    f[u].pb({wc, k, dist});
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        get_dist(j, u, k, dist + w[i], wc, p);
    }
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        sum += t;
        chkmax(ms, t);
    }
    chkmax(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void calc(int u) {
    if (st[u]) return ;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    for (int i = h[u], k = 0; ~i; i = ne[i]) {
        int j = e[i];
        auto &p = son[u][k];
        get_dist(j, u, k, w[i], u, p);
        k ++ ;
        p.pb({-1, 0}), p.pb({K + 1, 0});
        sort(p.begin(), p.end());
        for (int i = 0; i < (int)p.size(); i ++ ) p[i].dist += p[i - 1].dist;
    }
    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}

LL query(int u, int l, int r) {
    LL res = 0;
    for (auto &t : f[u]) { //枚举u所在的所有重心 再枚举这些重心的所有子树
        if (age[t.wc] >= l && age[t.wc] <= r) res += t.dist;
        for (int i = 0; i < 3; i ++ ) {
            if (i == t.id) continue;
            auto &p = son[t.wc][i];
        //  if (p.size() == 2) continue;
            if (!p.size()) continue;
            int a = lower_bound(p.begin(), p.end(), (Son){l, -1}) - p.begin();
            int b = lower_bound(p.begin(), p.end(), (Son){r + 1, -1}) - p.begin();
            res += t.dist * (b - a) + p[b - 1].dist - p[a - 1].dist; //还要加上b-a个重心到u的距离
        }
    }
    //u作为重心时的答案
    for (int i = 0; i < 3; i ++ ) {
        auto &p = son[u][i];
        //if (p.size() == 2) continue;
        if (!p.size()) continue;
        int a = lower_bound(p.begin(), p.end(), (Son){l, -1}) - p.begin();
        int b = lower_bound(p.begin(), p.end(), (Son){r + 1, -1}) - p.begin();
        res += p[b - 1].dist - p[a - 1].dist;
    }
    return res;
}

int main() { 
    cin >> n >> m >> K;
    for (int i = 1; i <= n; i ++ ) read(age[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    calc(1);
    LL res = 0, L, R;
    while (m -- ) {
        int u, a, b; read(u), read(a), read(b);
        L = min((a + res) % K, (b + res) % K), R = max((a + res) % K, (b + res) % K);
        if (L > R) swap(L, R);
        cout << (res = query(u, L, R)) << '\n';
    }
    return 0;
}



Crescent
19天前

点分治

1.
求树上长度不超过 K 的路径有多少条

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10, M = N << 1;

int n, K, e[M], h[N], idx, ne[M], w[M];
int q[N], p[N];
bool st[N];

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

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        sum += t;
        ms = max(ms, t);
    }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void get_dist(int u, int fa, int dist, int &qt) {
    if (st[u]) return ;
    q[ ++ qt] = dist;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        get_dist(j, u, dist + w[i], qt);
    }
}
int get(int a[], int k) {
    sort(a + 1, a + 1 + k);
    int res = 0;
    for (int i = 1, j = k; j >= 1; j -- ) {
        while (i < j && a[i] + a[j] <= K) i ++ ;
        if (i < j) res += i - 1;
        else res += j - 1;
    }
    return res;
}

int calc(int u) {
    if (st[u]) return 0;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    int pt = 0, res = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], qt = 0;
        get_dist(j, -1, w[i], qt);
        res -= get(q, qt);
        for (int k = 1; k <= qt; k ++ ) {
            if (q[k] <= K) res ++ ;
            p[ ++ pt] = q[k];
        }
    }
    res += get(p, pt);
    for (int i = h[u]; ~i; i = ne[i]) res += calc(e[i]);
    return res;
}

int main() {
    while (cin >> n >> K, n || K) {
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        idx = 0;
        for (int i = 1; i < n; i ++ ) {
            int a, b, c; cin >> a >> b >> c;
            add(a, b, c), add(b, a, c);
        }
        cout << calc(1) << '\n';
    }
}

2.P3714 [BJOI2017]树的难题
遍历到某棵子树的某条路径时 设经过的边数为c, 当前子树连向重心的边的颜色为cl,当前路径的权值为v
则为了更新答案 还需要知道所有经过边数属于[l - c, r - c]的不同子树的路径中 连向重心
的边的颜色不为cl的最大权值v1和颜色同为cl的最大权值v2,比较max(v+v1,v+v2-w[cl]) 更新答案
显然可以将边数作为下标 用线段树维护区间最大值, 对于颜色 可以对于每个点的所有边按照颜色排序
这样我们遍历一个重心的所有点时,对于相同颜色的初边一定是连续处理的,
开两个线段树维护其他颜色和当前颜色的权值即可 O(nlog^2)
单调队列按秩合并可以一个log

const int N = 2e5 + 10, M = N << 1, INF = 2e9;

int n, m, L, R, h[N], e[M], ne[M], w[M], v[N], sz[N], S, maxP, pos, idx;
int res = -INF, q[N];
bool st[N];
pi p[N];

struct Tree {
    #define ro tr[u]
    #define lc tr[u].l
    #define rc tr[u].r
    int rt0, rt1, idx;
    struct Node {
        int l, r, v;
    } tr[N * 40];
    void modify(int &u, int l, int r, int x, int c) {
        if (!u) tr[u = ++ idx] = {0, 0, -INF};
        chkmax(ro.v, c);
        if (l == r) return ;
        int mid = l + r >> 1;
        if (x <= mid) modify(lc, l, mid, x, c);
        else modify(rc, mid + 1, r, x, c);
    }
    int query(int u, int l, int r, int x, int y) {
        if (x > y) return -INF;
        if (!u) return -INF;
        if (l >= x && r <= y) return ro.v;
        int mid = l + r >> 1, res = -INF;
        if (x <= mid) res = query(lc, l, mid, x, y);
        if (y > mid) chkmax(res, query(rc, mid + 1, r, x, y));
        return res;
    }
    void merge(int &u, int &v, int l, int r) {
        if (!u) { u = v; return; }
        if (!v) return ;
        chkmax(tr[u].v, tr[v].v);
        if (l == r) return ;
        int mid = l + r >> 1;
        merge(lc, tr[v].l, l, mid); merge(rc, tr[v].r, mid + 1, r);
    }
}T;

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

void get_wc(int u, int fa, int &wc) {
    sz[u] = 1; int ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa || st[j]) continue;
        get_wc(j, u, wc);
        chkmax(ms, sz[j]);
        sz[u] += sz[j];
    }
    chkmax(ms, S - sz[u]);
    if (ms < maxP) wc = u, maxP = ms;
}

void get_dist(int u, int fa, int now, int last, int dist, int cnt, int &qt) {
    if (cnt > R) return ;
    chkmax(qt, cnt);
    q[cnt] = max(q[cnt], dist);
    chkmax(res, dist + T.query(T.rt0, 1, n, max(1, L - cnt), min(n, R - cnt))); //其他颜色
    chkmax(res, dist + T.query(T.rt1, 1, n, max(1, L - cnt), min(n, R - cnt)) - v[now]);
    if (cnt >= L && cnt <= R) chkmax(res, dist);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], cl = w[i];
        if (j == fa || st[j]) continue; 
        get_dist(j, u, now, cl, dist + (cl == last ? 0 : v[cl]), cnt + 1, qt);
    }
}

void calc(int u) {
    if (S == 1) return ;
    maxP = N, get_wc(u, -1, u), st[u] = true;
    int pt = 0; T.idx = T.rt0 = T.rt1 = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (st[j]) continue;
        p[ ++ pt] = {w[i], j};
    }
    sort(p + 1, p + 1 + pt);
    for (int i = 1; i <= pt; i ++ ) {
        int j = p[i].se, cl = p[i].fi, qt = 0;
        get_dist(j, u, cl, cl, v[cl], 1, qt);
        for (int k = 1; k <= qt; k ++ ) {
            T.modify(T.rt1, 1, n, k, q[k]);
            q[k] = -INF;
        }
        if (i < pt && cl != p[i + 1].fi) {
            T.merge(T.rt0, T.rt1, 1, n);
            T.rt1 = 0;
        }
    }
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (st[j]) continue;
        S = sz[j]; calc(j);
    }
}



int main() {
    cin >> n >> m >> L >> R;
    for (int i = 1; i <= m; i ++ ) read(v[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    S = n;
    for (int i = 1; i <= n; i ++ ) q[i] = -INF;
    calc(1);
    cout << res;
    return 0;
}

动态点分治:

如果树的结构不变 且多组询问的点不同 可以先预处理出所有的重心与信息
1.开店
题意:一棵树,有点权有边权,统计点权在[l, r]之间的所有点到u的距离之和 u有多组询问,强制在线
对于u,答案为除u所在子树的所有子树中的点到u的距离贡献+u所在子树的所有贡献+重心到u的贡献
前一个贡献可以将所有距离和对应的年龄存下来,按年龄排序,二分出l, r 用前缀和统计贡献
后一个贡献可以递归处理u所在子树,不断减小u所在子树的大小,重复上面的操作,
直到u为重心为止,统计统计u的所有子树的贡献结束
动态点分治:如果树的结构不发生变化 先预处理出所有会用到的重心
将每个重心连接到的所有子树的信息存在重心里面,记录信息所在子树的编号
同时记录每个点在哪些重心的管辖中,枚举这些重心的信息,统计除u所在子树的所有距离对u产生的贡献

const int N = 1.5e5 + 10, M = N << 1, Q = 2e5 + 10;

int n, m, h[N], e[M], ne[M], w[M], K, idx, age[N];
bool st[N];

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

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

struct Son {
    int age;
    LL dist;
    bool inline operator< (const Son &b) const {
        return age < b.age;
    }
};
vector<Son> son[N][3];
struct Fa {
    int wc, id;
    LL dist;
};
vector<Fa> f[N];
void get_dist(int u, int fa, int k, LL dist, int &wc, vector<Son> &p) {
    if (st[u]) return ;
    p.pb({age[u], dist});
    f[u].pb({wc, k, dist});
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        get_dist(j, u, k, dist + w[i], wc, p);
    }
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        sum += t;
        chkmax(ms, t);
    }
    chkmax(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void calc(int u) {
    if (st[u]) return ;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    for (int i = h[u], k = 0; ~i; i = ne[i]) {
        int j = e[i];
        auto &p = son[u][k];
        get_dist(j, u, k, w[i], u, p);
        k ++ ;
        p.pb({-1, 0}), p.pb({K + 1, 0});
        sort(p.begin(), p.end());
        for (int i = 0; i < (int)p.size(); i ++ ) p[i].dist += p[i - 1].dist;
    }
    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}

LL query(int u, int l, int r) {
    LL res = 0;
    for (auto &t : f[u]) { //枚举u所在的所有重心 再枚举这些重心的所有子树
        if (age[t.wc] >= l && age[t.wc] <= r) res += t.dist;
        for (int i = 0; i < 3; i ++ ) {
            if (i == t.id) continue;
            auto &p = son[t.wc][i];
        //  if (p.size() == 2) continue;
            if (!p.size()) continue;
            int a = lower_bound(p.begin(), p.end(), (Son){l, -1}) - p.begin();
            int b = lower_bound(p.begin(), p.end(), (Son){r + 1, -1}) - p.begin();
            res += t.dist * (b - a) + p[b - 1].dist - p[a - 1].dist; //还要加上b-a个重心到u的距离
        }
    }
    //u作为重心时的答案
    for (int i = 0; i < 3; i ++ ) {
        auto &p = son[u][i];
        //if (p.size() == 2) continue;
        if (!p.size()) continue;
        int a = lower_bound(p.begin(), p.end(), (Son){l, -1}) - p.begin();
        int b = lower_bound(p.begin(), p.end(), (Son){r + 1, -1}) - p.begin();
        res += p[b - 1].dist - p[a - 1].dist;
    }
    return res;
}

int main() { 
    cin >> n >> m >> K;
    for (int i = 1; i <= n; i ++ ) read(age[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    calc(1);
    LL res = 0, L, R;
    while (m -- ) {
        int u, a, b; read(u), read(a), read(b);
        L = min((a + res) % K, (b + res) % K), R = max((a + res) % K, (b + res) % K);
        if (L > R) swap(L, R);
        cout << (res = query(u, L, R)) << '\n';
    }
    return 0;
}

wating
1.
容斥

// Problem: P5306 [COCI2019] Transport
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5306
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 10, M = N << 1;

int n, h[N], e[M], w[M], ne[M], sz[N], maxP, S, A[N], idx;
LL q1[N], q2[N], p1[N], p2[N], res, ans;
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 get_wc(int u, int fa, int &wc) {
    sz[u] = 1; int ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa || st[j]) continue;
        get_wc(j, u, wc);
        sz[u] += sz[j];
        chkmax(ms, sz[j]);
    }
    chkmax(ms, S - sz[u]);
    if (ms < maxP) maxP = ms, wc = u;
}

void get_dist(int u, int fa, LL dist1, LL dist2, int &qt) {
    q1[ ++ qt] = dist1, q2[qt] = dist2;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa || st[j]) continue;
        LL c1 = dist1 + A[u] - w[i]; //out
        LL c2 = dist2 + A[j] - w[i]; //in
        get_dist(j, u, c1, c2, qt);
    }
}
void calc(int u) {
    if (S == 1) return ;
    maxP = N; get_wc(u, -1, u);
    st[u] = true;
    int pt = 0; LL ans = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], qt = 0; if (st[j]) continue;
        get_dist(j, u, A[u] - w[i], A[j] - w[i], qt);
        sort(q1 + 1, q1 + 1 + qt);
        ans -= 1ll * qt * (qt - 1);
        for (int k = 1; k <= qt; k ++ ) { //q->p
            if (q2[k] < 0) ans -= pt + 1; //+1是只有一边的情况
            else {
                ans -= lower_bound(p1 + 1, p1 + 1 + pt, -q2[k]) - p1 - 1;
            }
        }
        for (int k = 1; k <= pt; k ++ ) { //p->q
            if (p2[k] < 0) ans -= qt;
            else {
                ans -= lower_bound(q1 + 1, q1 + 1 + qt, -p2[k]) - q1 - 1;
            }
        }
        // for (int k = 1; k <= pt; k ++ ) cout << p[k] << ' '; cout << endl;
        for (int k = 1; k <= qt; k ++ ) {
            ++ pt;
            p1[pt] = q1[k]; //out
            p2[pt] = q2[k];
        }
        sort(p1 + 1, p1 + 1 + pt);
    }
    res += max(0ll, 1ll * pt * (pt - 1) + ans);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (st[j]) continue;
        S = sz[j]; 
        calc(j);
    }
}
int main() {
    // 考虑点p作为重心 u->p->v 只要在u到v这条路径上任意两个点满足路径和>燃料和 这条路径就非法
    // 考虑容斥,所有可能的点对减去删去所有不符合的情况即可
    cin >> n;
    for (int i = 1; i <= n; i ++ ) read(A[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    S = n;
    calc(1);
    cout << res;
    return 0;
}


活动打卡代码 AcWing 264. 权值

Crescent
20天前
// Problem: 权值
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/266/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 2e5 + 10, S = 1e6 + 10, M = N << 1, INF = N;

int n, m, h[N], e[M], w[M], ne[M], idx, f[S];
int res = INF;
bool st[N];
pi q[N], p[N];

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

void get_dist(int u, int fa, int dist, int cnt, int &qt) {
    if (st[u] || dist > m) return ;
    q[ ++ qt] = {dist, cnt};
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        get_dist(j, u, dist + w[i], cnt + 1, qt);
    }
}

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        chkmax(ms, t);
        sum += t;
    }
    chkmax(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void calc(int u) {
    if (st[u]) return ;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    int pt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], qt = 0;
        get_dist(j, u, w[i], 1, qt);
        for (int k = 1; k <= qt; k ++ ) {
            auto& t = q[k];
            if (t.fi == m) chkmin(res, t.se);
            chkmin(res, t.se + f[m - t.fi]);
            p[ ++ pt] = t;
        }
        for (int k = 1; k <= qt; k ++ ) {
            auto& t = q[k];
            chkmin(f[t.fi], t.se);
        }
    }
    //回溯
    for (int i = 1; i <= pt; i ++ )
        f[p[i].fi] = INF;   
    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}


int main() {
    //f[i]=j表示距离重心长度为i的点最少经过j条边到达
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    memset(f, 0x3f, sizeof f);
    calc(1);
    if (res == INF) res = -1;
    cout << res;
    return 0;
}


活动打卡代码 AcWing 252. 树

Crescent
20天前
// Problem: 树
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/254/
// Memory Limit: 10 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 10, M = N << 1;

int n, K, q[N], p[N], idx, h[N], e[M], ne[M], w[M];
bool st[N];

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

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        chkmax(ms, t);
        sum += t;
    }
    chkmax(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void get_dist(int u, int fa, int dist, int &qt) {
    if (st[u]) return ; //防止往回搜到重心
    q[ ++ qt] = dist;
    for (int i = h[u]; ~i; i = ne[i]) 
        if (e[i] != fa) get_dist(e[i], u, dist + w[i], qt);
}

int get(int a[], int k) {
    sort(a + 1, a + k + 1);
    int res = 0;
    for (int i = 1, j = k; j >= 1; j -- ) {
        while (a[i] + a[j] <= K && i < j) i ++ ;
        if (i < j) res += i - 1;
        else res += j - 1;
    }
    return res;
}

int calc(int u) {
    if (st[u]) return 0;
    int res = 0;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;

    int pt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], qt = 0;
        get_dist(j, -1, w[i], qt);
        res -= get(q, qt); //第3类路径
        for (int k = 1; k <= qt; k ++ ) {
            if (q[k] <= K) res ++ ; //处理第1类路径
            p[ ++ pt] = q[k];
        } 
    }
    res += get(p, pt); 
    for (int i = h[u]; ~i; i = ne[i]) res += calc(e[i]);
    return res;
}

int main() {
    // 点分治+容斥 将路径分为3种 1.树内与重心 2.跨过重心在两棵子树内 3.在同一棵子树内
    // 第3种递归查询 第1种获得每科子树的所有距离时记录 对于第2种:考虑容斥 将除了重心之外
    // 的所有子树中的点加入一个数组 求该数组的任意两点可以组成的答案再减去两点处于同一棵
    // 子树的答案就是该答案
    while (cin >> n >> K, n || K) {
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        idx = 0;
        for (int i = 1; i < n; i ++) {
            int a, b, c; read(a), read(b), read(c);
            add(a, b, c), add(b, a, c);
        }
        cout << calc(1) << '\n';
    }
    return 0;
}


活动打卡代码 AcWing 2847. 老C的任务

Crescent
30天前
// Problem: 老C的任务
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2849/
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 5e5 + 10;

int n, m;
LL res[N];

struct E {
    int x, y, z, v, sign, id;
    LL ans;
    inline bool operator< (const E &t) {
        if (x != t.x) return x < t.x;
        if (y != t.y) return y < t.y;
        return z < t.z;
    }
}e[N], d[N];

void cdq(int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    LL sv = 0;
    for (int j = mid + 1, i = l, k = l; k <= r; k ++ ) {
        if (j > r || (i <= mid && e[i].y <= e[j].y)) {
            sv += e[i].v; d[k] = e[i ++ ];
        } else {
            e[j].ans += e[j].sign * e[j].z * sv; d[k] = e[j ++ ];
        }
    }
    for (int j = l; j <= r; j ++ ) e[j] = d[j];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        int x, y, p;
        read(x), read(y), read(p);
        e[i] = {x, y, 0, p};
    }
    int idx = n;
    for (int i = 1; i <= m; i ++ ) {
        int a, b, c, d;
        read(a), read(b), read(c), read(d);
        e[ ++ idx] = {a - 1, b - 1, 1, 0, 1, i};
        e[ ++ idx] = {a - 1, d, 1, 0, -1, i};
        e[ ++ idx] = {c, b - 1, 1, 0, -1, i};
        e[ ++ idx] = {c, d, 1, 0, 1, i};
    }   
    sort(e + 1, e + 1 + idx);
    cdq(1, idx);
    for (int i = 1; i <= idx; i ++ ) 
        res[e[i].id] += e[i].ans;
    for (int i = 1; i <= m; i ++ ) 
        cout << res[i] << '\n';
    return 0;
}



Crescent
1个月前

1.P3157 [CQOI2011]动态逆序对
一维为编号(自带) 二维为权值(排序) 三维为时间(BIT)
[l, r]区间中 [l, mid]的逆序对为[mid+1, r]中权值小于且时间大于他的数
对于[mid+1, r]中的数,逆序对为[l,mid]中权值大于且时间大于他的数 又权值
升序排序故对于[l,mid] i从l开始r从mid+1开始 对于[mid+1,r] i从mid开始 j从r开始
这题用分块套bit也可以

const int N = 1e5 + 10, M = 5e4 + 10;

int n, m, K, pos[N], c[N], ans[M];

struct E {
    int v, t;
    bool operator< (const E &t) const {
        return v < t.v;
    }
}e[N], d[N];

void inline add(int x, int k) {
    for (; x <= K; x += x & -x) c[x] += k;
}

int inline ask(int x) {
    int res = 0;
    for (; x; x -= x & -x) res += c[x];
    return res;
}

void inline del(int x) {
    for (; x <= K; x += x & -x) c[x] = 0;
}

void cdq(int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    for (int i = l, j = mid + 1; i <= mid; i ++ ) {
        while (j <= r && e[j].v < e[i].v) add(e[j ++ ].t, 1);
        ans[e[i].t] += ask(m + 1) - ask(e[i].t);
    }   
    for (int j = mid + 1; j <= r; j ++ ) del(e[j].t);
    for (int i = r, j = mid; i >= mid + 1; i -- ) {
        while (j >= l && e[j].v > e[i].v) add(e[j -- ].t, 1);
        ans[e[i].t] += ask(m + 1) - ask(e[i].t);
    }
    for (int j = l; j <= mid; j ++ ) del(e[j].t);
    for (int i = l, j = mid + 1, k = l; k <= r; k ++ ) {
        if (j > r || (i <= mid && e[j].v > e[i].v)) d[k] = e[i ++ ];
        else d[k] = e[j ++ ];
    }
    for (int i = l; i <= r; i ++ ) e[i] = d[i];
    //sort(e + l, e + r + 1);  //不开O2的话sort比临时数组慢很多
}

int main() {
     cin >> n >> m;
     for (int i = 1; i <= n; i ++ ) {
        int x;
        read(x);
        e[i] = {x, m + 1};
        pos[x] = i;
     }
     for (int i = 1; i <= m; i ++ ) {
        int x;
        read(x);
        e[pos[x]].t = i;
     }
     K = n;
     LL res = 0;
     for (int i = n; i; i -- ) {
        res += ask(e[i].v);
        add(e[i].v, 1);
     }
     memset(c, 0, sizeof c);
     K = m + 1;
     cdq(1, n);
     cout << res << '\n';
     for (int i = 1; i < m; i ++ ) {
        res -= ans[i];
        cout << res << '\n';
     }
     return 0;
}


活动打卡代码 AcWing 2819. 动态逆序对

Crescent
1个月前
// Problem: P3157 [CQOI2011]动态逆序对
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3157
// Memory Limit: 500 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 10, M = 5e4 + 10;

int n, m, K, pos[N], c[N], ans[M];

struct E {
    int v, t;
    bool operator< (const E &t) const {
        return v < t.v;
    }
}e[N], d[N];

void inline add(int x, int k) {
    for (; x <= K; x += x & -x) c[x] += k;
}

int inline ask(int x) {
    int res = 0;
    for (; x; x -= x & -x) res += c[x];
    return res;
}

void inline del(int x) {
    for (; x <= K; x += x & -x) c[x] = 0;
}

void cdq(int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    for (int i = l, j = mid + 1; i <= mid; i ++ ) {
        while (j <= r && e[j].v < e[i].v) add(e[j ++ ].t, 1);
        ans[e[i].t] += ask(m + 1) - ask(e[i].t);
    }   
    for (int j = mid + 1; j <= r; j ++ ) del(e[j].t);
    for (int i = r, j = mid; i >= mid + 1; i -- ) {
        while (j >= l && e[j].v > e[i].v) add(e[j -- ].t, 1);
        ans[e[i].t] += ask(m + 1) - ask(e[i].t);
    }
    for (int j = l; j <= mid; j ++ ) del(e[j].t);
    for (int i = l, j = mid + 1, k = l; k <= r; k ++ ) {
        if (j > r || (i <= mid && e[j].v > e[i].v)) d[k] = e[i ++ ];
        else d[k] = e[j ++ ];
    }
    for (int i = l; i <= r; i ++ ) e[i] = d[i];
    //sort(e + l, e + r + 1);  //开O2用sort快 否则sort远不如临时数组
}

int main() {
     // 一维为编号(自带) 二维为权值(排序) 三维为时间(BIT) 
     // [l, r]区间中 [l, mid]的逆序对为[mid+1, r]中权值小于且时间大于他的数
     // 对于[mid+1, r]中的数,逆序对为[l,mid]中权值大于且时间大于他的数 又权值
     // 升序排序故对于[l,mid] i从l开始r从mid+1开始 对于[mid+1,r] i从mid开始
     // j从r开始
     cin >> n >> m;
     for (int i = 1; i <= n; i ++ ) {
        int x;
        read(x);
        e[i] = {x, m + 1};
        pos[x] = i;
     }
     for (int i = 1; i <= m; i ++ ) {
        int x;
        read(x);
        e[pos[x]].t = i;
     }
     K = n;
     LL res = 0;
     for (int i = n; i; i -- ) {
        res += ask(e[i].v);
        add(e[i].v, 1);
     }
     memset(c, 0, sizeof c);
     K = m + 1;
     cdq(1, n);
     cout << res << '\n';
     for (int i = 1; i < m; i ++ ) {
        res -= ans[i];
        cout << res << '\n';
     }
     return 0;
}


活动打卡代码 AcWing 2815. 三维偏序

Crescent
1个月前
// Problem: P3810 【模板】三维偏序(陌上花开)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3810
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 10, M = 2e5 + 10;

int n, k, c[M], tot, res[N], K;

struct E {
    int a, b, c, w, ans;
    inline bool operator< (const E &t) const {
        if (a != t.a) return a < t.a;
        if (b != t.b) return b < t.b;
        return c < t.c;
    }
    inline bool operator== (const E &t) const {
        return (a == t.a && b == t.b && c == t.c);
    }
}e[N], d[N];

inline void add(int x, int k) {
    for (; x <= K; x += x & -x) c[x] += k;
}

inline int ask(int x) {
    int res = 0;
    for (; x; x -= x & -x) res += c[x];
    return res;
}

void cdq(int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    for (int i = l, j = mid + 1, k = l; k <= r; k ++ ) {
        if (j > r || (i <= mid && e[i].b <= e[j].b)) add(e[i].c, e[i].w), d[k] = e[i ++ ];
        else {
            e[j].ans += ask(e[j].c), d[k] = e[j ++ ];
        }
    }
    for (int i = l; i <= mid; i ++ ) add(e[i].c, -e[i].w);
    for (int i = l; i <= r; i ++ ) e[i] = d[i];
}

/* 写法2 会慢不少
void cdq(int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int k = l - 1;
    for (int i = l, j = mid + 1; j <= r; j ++ ) {
        while (i <= mid && e[i].b <= e[j].b) add(e[i].c, e[i].w), k = i ++ ;
        e[j].ans += ask(e[j].c);
    }
    for (int i = l; i <= k; i ++ ) add(e[i].c, -e[i].w);
    sort(e + l, e + r + 1, cmp2); //cmp2表示将b升序
}
*/
int main() {
    // 先对a排序 然后对b归并排序 双指针移动 再用树状数组维护c的个数 K比较小不用离散化 否则
    // 应该对c离散化
    cin >> n >> K;
    for (int i = 1; i <= n; i ++ ) {
        int a, b, c;
        read(a), read(b), read(c);
        e[i] = {a, b, c, 1};
    }
    sort(e + 1, e + 1 + n);
    for (int i = 1; i <= n; i ++ ) {
        if (e[i] == e[tot]) e[tot].w ++ ;
        else e[ ++ tot] = e[i];
    }
    cdq(1, tot);
    for (int i = 1; i <= tot; i ++ ) res[e[i].ans + e[i].w - 1] += e[i].w;
    for (int i = 0; i < n; i ++ ) cout << res[i] << '\n';
    return 0;
}


活动打卡代码 AcWing 2534. 树上计数2

Crescent
1个月前
// Problem: 树上计数2
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2536/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 4e4 + 10, M = 1e5 + 10, S = 16;

int n, m, len, dfn[M], w[N], A[N], L[N], R[N], fa[N], ans[M], top[N], son[N], sz[N];
int h[N], ne[M], e[M], idx, cnt[N], res, ol, d[N], pos[N];
bool st[N];

struct Q {
    int id, l, r, c;
    bool operator< (const Q &b) const {
        if (pos[l] != pos[b.l]) return pos[l] < pos[b.l];
    //  return (i & 1) ? r < b.r : r > b.r;
        return r < b.r;
    }
}q[M];


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

void dfs1(int u, int f, int x) {
    dfn[L[u] = ++ ol] = u, sz[u] = 1, fa[u] = f, d[u] = x;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == f) continue;
        dfs1(j, u, x + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
    dfn[R[u] = ++ ol] = u;
}

void dfs2(int u, int t) {
    top[u] = t;
    if (!son[u]) return ; dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (d[top[u]] < d[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return d[u] > d[v] ? v : u;
}

void add(int x) { //x为欧拉序 不是权值
    if (st[x]) { //这个点出现两次 即将消失
        res -= ! -- cnt[w[x]];
    } else {
        res += ! cnt[w[x]] ++ ;
    }
    st[x] ^= 1;
}


int main() {
    // 1.离散化 2.求欧拉序列 3.求lca 4.莫队
    cin >> n >> m;
    len = (n + n) / sqrt(m);
    for (int i = 1; i <= 2 * n; i ++ ) pos[i] = (i + len - 1) / len;
    for (int i = 1; i <= n; i ++ ) read(w[i]), A[i] = w[i];
    sort(A + 1, A + 1 + n);
    int tot = unique(A + 1, A + 1 + n) - A - 1;
    for (int i = 1; i <= n; i ++ ) w[i] = lower_bound(A + 1, A + 1 + tot, w[i]) - A;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b; read(a), read(b);
        add(a, b), add(b, a);
    }
    dfs1(1, -1, 1), dfs2(1, 1);
    for (int i = 1, a, b; i <= m; i ++ ) {
        read(a), read(b);
        if (L[a] > L[b]) swap(a, b);
        int c = lca(a, b);
        if (c == a) q[i] = {i, L[a], L[b]};
        else q[i] = {i, R[a], L[b], c};
    }
    sort(q + 1, q + 1 + m);
    for (int k = 1, i = 0, j = 1; k <= m; k ++ ) {
        int id = q[k].id, c = q[k].c, l = q[k].l, r = q[k].r;
        while (i < r) add(dfn[ ++ i]);
        while (i > r) add(dfn[i -- ]);
        while (j < l) add(dfn[j ++ ]);
        while (j > l) add(dfn[ -- j]);
        if (c) add(c);
        ans[id] = res;
        if (c) add(c);
    }
    for (int i = 1; i <= m; i ++ ) cout << ans[i] << '\n';
    return 0;
}