제출 #1338909

#제출 시각아이디문제언어결과실행 시간메모리
1338909nguyenkhangninh99Tourism (JOI23_tourism)C++20
100 / 100
370 ms52496 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 1e5 + 5;
int tin[maxn], sz[maxn], h[maxn], c[maxn], timedfs;
int up[20][maxn], head[maxn];
vector<int> g[maxn];

void dfs(int u, int p){
    tin[u] = ++timedfs;
    up[0][u] = p;
    sz[u] = 1;
    for(int i = 1; i <= 19; i++) up[i][u] = up[i - 1][up[i - 1][u]];

    for(int v: g[u]){
        if(v != p){
            h[v] = h[u] + 1;
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
}
void hld(int u, int p){
    int mx = 0;
    for(int v: g[u]) if(v != p && sz[v] > sz[mx]) mx = v;
    for(auto v: g[u]){
        if(v == p) continue;
        head[v] = (v == mx ? head[u] : v);
        hld(v, u);
    }
}
int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int k = h[u] - h[v];
    for(int i = 0; i <= 19; i++){
        if(k & (1 << i)) u = up[i][u];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--){
        if(up[i][u] != up[i][v]) u = up[i][u], v = up[i][v];
    }
    return up[0][u];
}
int sp[20][maxn], st[4 * maxn], res[maxn];
void update(int id, int l, int r, int p, int val){
    if(l == r) st[id] += val;
    else{
        int mid = (l + r) / 2;
        if(p <= mid) update(id * 2, l, mid, p, val);
        else update(id * 2 + 1, mid + 1, r, p, val);
        st[id] = st[id * 2] + st[id * 2 + 1];
    }
}
int get(int id, int l, int r, int u, int v){
    if(v < l || r < u) return 0;
    if(u <= l && r <= v) return st[id];
    else{
        int mid = (l + r) / 2;
        return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
    }
}
int rangelca(int l, int r){
    int k = __lg(r - l + 1);
    return lca(sp[k][l], sp[k][r - (1 << k) + 1]);
}

vector<pair<int, int>> query[maxn], p[maxn];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i <= n - 1; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= m; i++) cin >> c[i];
    for(int i = 1; i <= q; i++){
        int l, r; cin >> l >> r;
        query[r].push_back({l, i});
    }

    dfs(1, 0);
    head[1] = 1;
    hld(1, 0);

    for(int i = 1; i <= m; i++) sp[0][i] = c[i];
    
    for(int i = 1; i <= 19; i++){
        for(int j = 1; j + (1 << i) - 1 <= m; j++) sp[i][j] = lca(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
    }

    for(int i = 1; i <= m; i++){
        int j = c[i];
        while(j){
            int last = h[head[j]];
            while(last <= h[j] && !p[head[j]].empty()){
                auto [len, col] = p[head[j]].back();
                if(len <= h[j]){
                    update(1, 1, m, col, -len + last - 1);
                    p[head[j]].pop_back();
                }
                else update(1, 1, m, col, -h[j] + last - 1);
                last = len + 1;
            }
            p[head[j]].push_back({h[j], i});
            update(1, 1, m, i, h[j] - h[head[j]] + 1);
            j = up[0][head[j]];
        }
        for(auto [l, id]: query[i]) res[id] = get(1, 1, m, l, i) - h[rangelca(l, i)];      
    }

    for(int i = 1; i <= q; i++) cout << res[i] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...