#include <stdio.h>
#include <stdlib.h>
int *mem(int i) { return (int *)calloc(i, sizeof(int)); }
int *remem(int *e, int i) { return (int*)realloc(e, sizeof(int) * i); }
void pus_(int **eh, int *eo, int x) {
int o = eo[0]++;
if (o == 0)
eh[0] = mem(2);
else if ((o & (o - 1)) == 0)
eh[0] = remem(eh[0], 2 * o);
eh[0][o++] = x;
}
#define pus(eh, eo, x) pus_(&(eh), &(eo), x)
int min(int i, int j) { return i < j ? i : j; }
int max(int i, int j) { return i > j ? i : j; }
#define QQ 100000
#define NN 100000
#define MM 100000
#define EE_ (2 * NN)
#define NN_ 100005
/*BEGINfenwick*/
int fw[NN_];
void upd(int p, int k) {
for (; p < NN_; p |= p + 1)
fw[p] += k;
}
long long qry(int p) {
if (p >= NN_)
p = NN_ - 1;
long long z = 0;
for (++p; p > 0; p &= p - 1)
z += fw[p - 1];
return z;
}
/*ENDfenwick*/
int tout[NN], Ans[QQ], N, M, Q, C[MM], L[QQ], R[QQ], X[NN], Y[NN], Freq[NN],
*Occ[NN]; /* Freq[u] = how many k such that C[k] = u , Occ[u] = that list of
ks */
/* BEGINoriginal tree*/
int *adj[NN], deg[NN];
int ii, dfn[NN], timer,
/*for lca, lca for virtual tree*/ dep[NN], jmp[NN], par[NN];
void tree_link(int u, int v) {
pus(adj[u], deg[u], v);
}
void tree_link_bi(int u, int v) {
tree_link(u, v), tree_link(v, u);
}
void dfs(int u, int p) {
dep[u] = dep[par[u] = p] + 1;
jmp[u] = (dep[p] - dep[jmp[p]] == dep[jmp[p]] - dep[jmp[jmp[p]]]) ? jmp[jmp[p]] : p;
dfn[u] = timer++;
for (int j = 0; j < deg[u]; ++j)
if (adj[u][j] - p)
dfs(adj[u][j], u);
tout[u] = timer - 1;
}
int lca(int u, int v) {
if (dep[u] < dep[v])
return lca(v, u);
while (dep[u] > dep[v])
u = (dep[jmp[u]] >= dep[v]) ? jmp[u] : par[u];
while (u - v)
if (jmp[u] == jmp[v])
u = par[u], v = par[v];
else
u = jmp[u], v = jmp[v];
return u;
}
/* END original tree*/
/*BEGIN virtual tree */
int *vtadj[NN], *vtw[NN], vtdeg[NN], vtdeg2[NN];
void virtual_link(int u, int v, int w) {
pus(vtadj[u], vtdeg[u], v);
pus(vtw[u], vtdeg2[u], w);
}
void virtual_link_bi(int u, int v, int w) { virtual_link(u, v, w), virtual_link(v, u, w); }
/*END virtualt ree*/
/* compare nodes by dfn time */
int Compar_Dfn(const void *i, const void *j) {
return dfn[*(const int *)i] - dfn[*(const int *)j];
}
/* in virtual tree, lef[u] stores highest k < m such that C[k] == u,
* analogously, rgt[u] = stores lowest k > m such that C[k] == u
* this is needed because, we take edge (x, y, w) in virtual tree (rooted at
* C[m]) if query_l <= x or query_r >= y
*
* note that if u is parent of v in virtual tree, even if v's timer more
* permissive than u's timer, we need to take v anyway, so a node's timer need
* to be set at least at strict as it's stricted children
*/
int lef[NN], rgt[NN];
int vt_up[NN]; /*weight of u, par[u] */
int C2(const void *i, const void *j) {
return lef[*(const int *)i] - lef[*(const int *)j];
}
int C3(const void *i, const void *j) {
return L[*(const int *)i] - R[*(const int *)j];
}
long long add_all = 0;
/* note on how to build virtual tree - sort all vertices in dfn order, insert
* lca of every consecutive element, uniqueify the new Vertex List, make the
* tree?? */
void vtdfs(int u, int p, int pw, int m) {
add_all += pw;
vt_up[u] = pw;
/* find upperbound(Occ[u], m); */
int lb = -1, ub = Freq[u];
while (ub - lb > 1) {
int mid = lb + (ub - lb) / 2;
if (Occ[u][mid] > m)
ub = mid;
else
lb = mid;
}
if (ub < Freq[u])
rgt[u] = Occ[u][ub] - 1;
if (ub) {
if (Occ[u][--ub] < m)
lef[u] = Occ[u][ub] + 1;
else if (ub && Occ[u][--ub] < m)
lef[u] = Occ[u][ub] + 1;
}
//printf(" At %d, LR = %d %d\n",u,lef[u],rgt[u]);
for (int j = 0; j < vtdeg[u]; ++j)
if (vtadj[u][j] != p) {
vtdfs(vtadj[u][j], u, vtw[u][j], m);
lef[u] = max(lef[u], lef[vtadj[u][j]]);
rgt[u] = min(rgt[u], rgt[vtadj[u][j]]);
}
}
int mark[NN] = {0}, dnc_timer = 0;
/* store active query for dnc, that is query i which L[i] <= m <= R[i] */
void dnc(
int l, int r, int *candidates,
int count_candidates) { /* calc answer for alll queries containing m */
if (l >= r) {
free(candidates);
return; /* ignore l=r because answer is always 1 (ql==qr)*/
}
int m = l + (r - l) / 2;
/* V = set of vertices in virtual tree , ord = |V| */
/* build a virtual tree for all node u that some l <= k <= r, C[k] = u */
/* collect all interested nodes */
int *V = NULL, ord = 0;
++dnc_timer;
for (int i = l; i <= r; ++i)
if (dnc_timer != mark[C[i]])
(mark[C[i]] = dnc_timer),
pus(V, ord, C[i]);
qsort(V, ord, sizeof *V, Compar_Dfn);
for (int orig_ord = ord, lc, i = 1; i < orig_ord; ++i)
if (dnc_timer != mark[lc = lca(V[i], V[i - 1])])
pus(V, ord, lc), mark[lc] = dnc_timer;
qsort(V, ord, sizeof *V, Compar_Dfn);
/* clear global related to virtual tree */
for (int i = 0; i < ord; ++i) {
free(vtadj[V[i]]);
free(vtw[V[i]]);
vtdeg[V[i]] = vtdeg2[V[i]] = 0;
}
/* build vt */
{
static int stack[NN << 1], top;
top = 0;
for (int i = 0; i < ord; ++i) {
int u = V[i];
while (top && !(dfn[stack[top - 1]] <= dfn[u] &&
tout[u] <= tout[stack[top - 1]]))
--top;
if (top)
virtual_link_bi(stack[top - 1], u, dep[u] - dep[stack[top - 1]]);
stack[top++] = u;
}
}
/* do dfs on vt to calculate lef and rgt */
for (int i = 0; i < ord; ++i)
lef[V[i]] = -2, rgt[V[i]] = 1e9 + 2;
add_all = 0;
vtdfs(C[m], -1, 0, m);
//printf(" HERE ! %d %d\n", l, r); printf(" Current |V| = %d\n", ord); printf(" : ");for(int i=0;i<ord;++i)printf(" %d : L = %d, R = %d\n", V[i],lef[V[i]],rgt[V[i]]);puts("");
/* collect all active queries, one that contain m (ql <= m <= qr) */
int *active = 0, nactive = 0, *left = 0, nleft = 0, *right = 0, nright = 0;
for (int i = 0; i < count_candidates; ++i) {
int j = candidates[i];
if (L[j] <= m && m <= R[j])
pus(active, nactive, j);
else if (R[j] < m)
pus(left, nleft, j);
else if (L[j] > m)
pus(right, nright, j);
}
free(candidates);
//printf (" Active queries (%d): ",nactive); for (int i=0;i<nactive;++i)printf("%d ",active[i]);puts("");
/* do fenwick to get answers */
/* for each node that is not C[m], the edge about it has (x, y, w)
* add w to each active querys, except ones that x < ql and qr < y
* by adding 1 to x, -1 to y
* that is add -w to the one that [x, y] cover [ql,qr]
* this can be done with sweepline (wtf)
*
* have a sum fenwick tree
* sort those (x, y, w) edges by increasing x [C2]
* also sort active querys by increasing ql [C3]
* do two pointer, and on edges, update -w to y,
* on queries, add sumfenwick(qr, N) to Ans[query]
*/
qsort(V, ord, sizeof *V, C2);
qsort(active, nactive, sizeof *active, C3);
int pi = 0, qi;
for (int i = 0; i < nactive; ++i) {
qi = active[i];
for (; pi < ord && lef[V[pi]] <= L[qi]; ++pi)
if (rgt[V[pi]] < 1e9)
upd(rgt[V[pi]], -vt_up[V[pi]]);
Ans[qi] += qry(NN_ - 1) - qry(R[qi] - 1);
Ans[qi] += add_all;
}
/* undo all fenwick upd (IM GONNA KILLL MYSELF AG IRUH */
pi = 0;
for (int i = 0; i < nactive; ++i) {
qi = active[i];
for (; pi < ord && lef[V[pi]] <= L[qi]; ++pi)
if (rgt[V[pi]] < 1e9)
upd(rgt[V[pi]], vt_up[V[pi]]);
}
free(V);
free(active);
/* continue dnc */
/* left = queries i in active such that R[i] < m,
* right = queries i in active such that L[i] > m; */
dnc(l, m, left, nleft);
dnc(m + 1, r, right, nright);
/* dont need to free left and right, since dnc() owns pointers */
}
int main() {
scanf("%d%d%d", &N, &M, &Q);
for (int i = 1, A, B; i < N; ++i)
scanf("%d%d", &A, &B), --A, --B, tree_link_bi(A, B);
dep[0] = 0, jmp[0] = par[0] = 0;
dfs(0, 0);
for (int i = 0; i < M; ++i)
scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
int *candidates = NULL, ncandidates = 0;
for (int i = 0; i < Q; ++i)
scanf("%d%d", L + i, R + i), --L[i], --R[i],
pus(candidates, ncandidates, i);
dnc(0, M - 1, candidates, ncandidates);
for (int i = 0; i < Q; ++i)
printf("%d\n", Ans[i] + 1);
}
/*
*
* https://codeforces.com/blog/entry/114003?#comment-1015100
*
* DNC
*
*/
Compilation message
tourism.c: In function 'main':
tourism.c:267:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
267 | scanf("%d%d%d", &N, &M, &Q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.c:269:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
269 | scanf("%d%d", &A, &B), --A, --B, tree_link_bi(A, B);
| ^~~~~~~~~~~~~~~~~~~~~
tourism.c:273:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
273 | scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
| ^~~~~~~~~~~~~~~~~~
tourism.c:276:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
276 | scanf("%d%d", L + i, R + i), --L[i], --R[i],
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
447 ms |
12052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Incorrect |
753 ms |
16728 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
