이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
refs:
https://codeforces.com/blog/entry/114003?#comment-1015100
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
vector<int> adj1[N];
struct lca_algo {
// LCA template (for graphs with 1-based indexing)
int LOG = 1;
vector<int> depth;
vector<vector<int>> up;
vector<int> tin, tout;
int timer = 1;
lca_algo() {
}
lca_algo(int n) {
lca_init(n);
}
void lca_init(int n) {
while ((1 << LOG) < n) LOG++;
up = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
depth = vector<int>(n + 1);
tin = vector<int>(n + 1);
tout = vector<int>(n + 1);
lca_dfs(1, -1);
}
void lca_dfs(int node, int par) {
tin[node] = timer++;
trav(child, adj1[node]) {
if (child == par) conts;
up[child][0] = node;
rep1(j, LOG - 1) {
up[child][j] = up[up[child][j - 1]][j - 1];
}
depth[child] = depth[node] + 1;
lca_dfs(child, node);
}
tout[node] = timer-1;
}
int lift(int u, int k) {
rep(j, LOG) {
if (k & (1 << j)) {
u = up[u][j];
}
}
return u;
}
int query(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int k = depth[u] - depth[v];
u = lift(u, k);
if (u == v) return u;
rev(j, LOG - 1, 0) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
u = up[u][0];
return u;
}
int get_dis(int u, int v) {
int lca = query(u, v);
return depth[u] + depth[v] - 2 * depth[lca];
}
bool is_ances(int u, int v){
return tin[u] <= tin[v] and tout[u] >= tout[v];
}
};
template<typename T>
struct fenwick {
int siz;
vector<T> tree;
fenwick() {
}
fenwick(int n) {
siz = n;
tree = vector<T>(n + 1);
}
int lsb(int x) {
return x & -x;
}
void build(vector<T> &a, int n) {
for (int i = 1; i <= n; ++i) {
int par = i + lsb(i);
tree[i] += a[i];
if (par <= siz) {
tree[par] += tree[i];
}
}
}
void pupd(int i, T v) {
while (i <= siz) {
tree[i] += v;
i += lsb(i);
}
}
T sum(int i) {
T res = 0;
while (i) {
res += tree[i];
i -= lsb(i);
}
return res;
}
T query(int l, int r) {
if (l > r) return 0;
T res = sum(r) - sum(l - 1);
return res;
}
};
lca_algo LCA;
vector<int> a(N);
vector<pii> adj2[N];
vector<int> mxl(N), mnr(N);
vector<array<int,3>> edge_contrib;
void dfs1(int u, int p){
for(auto [v,d] : adj2[u]){
if(v == p) conts;
dfs1(v,u);
amax(mxl[u],mxl[v]);
amin(mnr[u],mnr[v]);
edge_contrib.pb({mxl[v],mnr[v],d});
}
}
vector<int> ans(N);
vector<array<int,3>> here[N];
fenwick<int> fenw(N);
void go(int l, int r, vector<array<int,3>> queries){
if(l > r) return;
int mid = (l+r) >> 1;
vector<array<int,3>> queries_left, queries_right, queries_curr;
for(auto [ql,qr,id] : queries){
if(qr < mid){
queries_left.pb({ql,qr,id});
}
else if(ql > mid){
queries_right.pb({ql,qr,id});
}
else{
queries_curr.pb({ql,qr,id});
}
}
vector<pii> nodes;
for(int i = l; i <= r; ++i){
int u = a[i];
nodes.pb({LCA.tin[u],u});
}
sort(all(nodes));
int siz = sz(nodes);
rep(i,siz-1){
int lca = LCA.query(nodes[i].ss,nodes[i+1].ss);
nodes.pb({LCA.tin[lca],lca});
}
sort(all(nodes));
nodes.resize(unique(all(nodes))-nodes.begin());
siz = sz(nodes);
stack<int> stk;
stk.push(nodes[0].ss);
rep1(i,siz-1){
auto [ti,u] = nodes[i];
while(!LCA.is_ances(stk.top(),u)){
stk.pop();
}
assert(!stk.empty());
int p = stk.top();
int d = LCA.get_dis(p,u);
adj2[p].pb({u,d}), adj2[u].pb({p,d});
stk.push(u);
}
for(auto [ti,u] : nodes){
mxl[u] = 0;
mnr[u] = r+1;
}
for(int i = l; i < mid; ++i){
int u = a[i];
amax(mxl[u],i);
}
for(int i = mid+1; i <= r; ++i){
int u = a[i];
amin(mnr[u],i);
}
edge_contrib.clear();
int root = a[mid];
dfs1(root,-1);
for(auto [ql,qr,id] : queries_curr){
here[ql].pb({qr,id,1});
}
for(auto [lx,rx,w] : edge_contrib){
here[lx].pb({rx,w,2});
}
int sum = 0;
for(auto [lx,rx,w] : edge_contrib){
if(lx >= l){
sum += w;
}
else{
fenw.pupd(rx,w);
}
}
for(int ql = l; ql <= mid; ++ql){
trav(ar,here[ql]){
if(ar[2] == 1){
auto [qr,id,t] = ar;
int res = sum+fenw.query(1,qr)+1;
ans[id] = res;
}
else{
auto [rx,w,t] = ar;
sum -= w;
fenw.pupd(rx,w);
}
}
}
// reset
for(auto [ql,qr,id] : queries_curr){
here[ql].clear();
}
for(auto [lx,rx,w] : edge_contrib){
here[lx].clear();
}
for(auto [ti,u] : nodes){
adj2[u].clear();
}
for(auto [lx,rx,w] : edge_contrib){
fenw.pupd(rx,-w);
}
go(l,mid-1,queries_left);
go(mid+1,r,queries_right);
}
void solve(int test_case)
{
int n,m,q; cin >> n >> m >> q;
rep1(i,n-1){
int u,v; cin >> u >> v;
adj1[u].pb(v), adj1[v].pb(u);
}
rep1(i,m) cin >> a[i];
LCA = lca_algo(n);
vector<array<int,3>> queries;
rep1(i,q){
int l,r; cin >> l >> r;
queries.pb({l,r,i});
}
go(1,m,queries);
rep1(i,q) cout << ans[i] << endl;
}
int main()
{
fastio;
int t = 1;
// cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |