제출 #764211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764211		huutuan	Tourism (JOI23_tourism)	C++14	28 / 100	5043 ms	33120 KiB

tourism

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=1e5+1, S=320, LG=17;

struct query{
    int l, r, i;

    query(int a=0, int b=0, int c=0): l(a), r(b), i(c){}

    bool operator<(const query& x){
        return l/S!=x.l/S?l<x.l:r<x.r;
    }
} qq[N];

int n, m, q, a[N], tdfs, tin[N], tout[N], up[N][LG], dep[N], ans[N];
vector<int> g[N];

void dfs(int u){
    tin[u]=++tdfs;
    dep[u]=dep[up[u][0]]+1;
    for (int v:g[u]) if (v!=up[u][0]){
        up[v][0]=u;
        for (int k=1; k<LG; ++k) up[v][k]=up[up[v][k-1]][k-1];
        dfs(v);
    }
    tout[u]=tdfs;
}

int lca(int u, int v){
    if (dep[u]!=dep[v]){
        if (dep[u]<dep[v]) swap(u, v);
        int d=dep[u]-dep[v];
        for (int k=0; k<LG; ++k) if (d>>k&1) u=up[u][k];
    }
    if (u==v) return u;
    for (int k=LG-1; k>=0; --k) if (up[u][k]!=up[v][k]) u=up[u][k], v=up[v][k];
    return up[u][0];
}

void solve(int tc){
    // cout << "Case #" << tc << ": ";
    cin >> n >> m >> q;
    for (int i=1; i<n; ++i){
        int x, y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    for (int i=1; i<=m; ++i) cin >> a[i];
    for (int i=1; i<=q; ++i){
        int x, y; cin >> x >> y;
        qq[i]={x, y, i};
    }
    sort(qq+1, qq+q+1);
    multiset<pair<int, int>> st;
    int val=0;
    function<int(int, int)> calc=[&](int x, int y) -> int {
        return dep[y]-dep[lca(x, y)];
    };
    function<void(int)> add=[&](int x) -> void {
        if (st.empty()){
            st.emplace(tin[x], x);
            return;
        }
        auto it=st.lower_bound({tin[x], x});
        auto previt=it==st.begin()?prev(st.end()):prev(it);
        auto nextit=it==st.end()?st.begin():it;
        val-=calc(previt->second, nextit->second);
        val+=calc(previt->second, x);
        val+=calc(x, nextit->second);
        st.emplace(tin[x], x);
    };
    function<void(int)> del=[&](int x) -> void {
        if (sz(st)==1){
            st.erase({tin[x], x});
            return;
        }
        auto it=st.find({tin[x], x});
        auto previt=it==st.begin()?prev(st.end()):prev(it);
        auto nextit=it==prev(st.end())?st.begin():next(it);
        val+=calc(previt->second, nextit->second);
        val-=calc(previt->second, x);
        val-=calc(x, nextit->second);
        st.erase(it);
    };
    int cl=1, cr=0;
    for (int i=1; i<=q; ++i){
        int l=qq[i].l, r=qq[i].r;
        while (l<cl){
            --cl;
            add(a[cl]);
        }
        while (r>cr){
            ++cr;
            add(a[cr]);
        }
        while (l>cl){
            del(a[cl]);
            ++cl;
        }
        while (r<cr){
            del(a[cr]);
            --cr;
        }
        ans[qq[i].i]=val;
    }
    for (int i=1; i<=q; ++i) cout << ans[i]+1 << '\n';
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int ntests=1;
    // cin >> ntests;
    for (int i=1; i<=ntests; ++i) solve(i);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41