제출 #1306529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306529		ender_shayan	Tourism (JOI23_tourism)	C++20	18 / 100	5092 ms	15928 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

typedef long long ll;
typedef long double	ld;
typedef pair<int, int>	pii  ;
typedef pair<ll, ll>	pll  ;
typedef vector<pii>     vii  ;
typedef vector<int>     veci ;
typedef vector<pll>     vll  ;
typedef vector<ll>      vecll;

// find_by_order             order_of_key

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define lb              lower_bound
#define ub              upper_bound
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
#define forn(n)         for(int i=n;i>0;i--)
#define pq              priority_queue <pii, vector<pii>, greater<pii>>


const ll mod = 1e9+7 ;// 998244353 ;// 1e9+9;

ll inf=1e18;
const int N=1e5+100,L=17,bs=701,NN=1e6;
int A[N],B[N],C[N],D[N],E[N],n,m,k,q,dp[N],pre[N],dist[N],t,st[N],en[N],h[N],par[N][L];
bitset<N> is;
vector<int>g[N];

int ans;
ll fen[N];
void upd(int i,ll x){
    for(;i<=n;i+=i&-i)fen[i]+=x;
}
ll get(int i){
    ll ans=0;
    for(;i>0;i-=i&-i)ans+=fen[i];
    return ans;
}
ll get(int l,int r){
    return get(r)-get(l-1);
}
void dfs(int v){
    for(int j=1;j<L;j++)par[v][j]=par[par[v][j-1]][j-1];
    st[v]=++t;
    for(int u:g[v])if(u!=par[v][0]){
        h[u]=h[v]+1;
        par[u][0]=v;
        dfs(u);
    }
    en[v]=t;
}
int LCA(int v1,int v2){
    if(h[v1]<h[v2])swap(v1,v2);
    int x=h[v1]-h[v2];
    for(int j=0;j<L;j++)if(x>>j&1)v1=par[v1][j];
    if(v1==v2)return v1;
    for(int j=L-1;j>=0;j--)if(par[v1][j]!=par[v2][j]){
        v1=par[v1][j];
        v2=par[v2][j];
    }
    return par[v1][0];
}
bool cmp(int a,int b){
    return (st[a]<st[b]);
}
bool cmp2(int a,int b){
    return (h[a]>h[b]);
}
int main(){
    fast_io
    cin>>n>>m>>q;
    for1(n-1){
        int u,v;cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for1(m)cin>>B[i];
    h[1]=1;
    dfs(1);
    while(q--){
        int l,r;cin>>l>>r;
        sort(B+l,B+r+1,cmp);
        vector<int>nod;
        for(int i=l;i<=r;i++)nod.pb(B[i]);
        for(int i=l;i<=r-1;i++)nod.pb(LCA(B[i],B[i+1]));
        int mnn=N;
        sort(all(nod));nod.resize(unique(all(nod))-nod.begin());
        for(int v:nod)mnn=min(mnn,h[v]-1);
        sort(all(nod),cmp2);
        ll ans=0;
        for(int v:nod){
            ll x=get(st[v],en[v]);
            x=1-x;
            ans+=1ll*(h[v]-mnn)*x;
            upd(st[v],x);
        }
        cout<<ans<<endl;
        for(int v:nod){
            int x=get(st[v],en[v]);
            x=-x;
            upd(st[v],x);
        }
    }




}

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