#include <stdio.h>
#include <stdlib.h>
void pus_(int **eh, int *eo, int x) {
int o = eo[0]++;
if (o == 0)
eh[0] = (int*)malloc(2 * sizeof **eh);
else if ((o & (o - 1)) == 0)
eh[0] = (int*)realloc(eh[0], 2 * o * sizeof **eh);
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
/*BEGINfenwick*/
int fw[MM];
void fw_add(int p, int k) {
for (; p < sizeof fw / sizeof *fw; p |= p + 1)
fw[p] += k;
}
long long fw_sum(int p) {
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], 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 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];
if ((ub && Occ[u][--ub] < m) || (ub && Occ[u][--ub] < m))
lef[u] = Occ[u][ub];
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 Compar_Queries_QL_Decreasing(const void*a,const void*b) {
return L[*(const int*)b] - L[*(const int*)a];
}
int Compar_Edges_X_Decreasing(const void*a,const void*b) {
return lef[*(const int*)b] - lef[*(const int*)a];
}
void rev(int *a, int n) {
int t;
for (int l = 0, r = n - 1; l < r; ++l, --r)
t = a[l], a[l] = a[r], a[r] = t;
}
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)
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]]);
vtadj[V[i]] = vtw[V[i]] = NULL;
vtdeg[V[i]] = vtdeg2[V[i]] = NULL;
}
/* 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);
/* collect all active queries, one that contain m (ql <= m <= qr) */
int *active = NULL, nactive = 0,
*left = NULL, nleft = NULL,
*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);
/*
* we add w to queries that ql <= x or y <= qr
* that is , ql <= x , exclusive or (ql > x and y <= qr)
* */
/* sort active by ql */
/* ql <= x */
qsort(active, nactive, sizeof(int), Compar_Queries_QL_Decreasing);
qsort(V, ord, sizeof(int), Compar_Edges_X_Decreasing);
int pi = 0, sum = 0;
for (int i = 0; i < nactive; ++i) {
int qi = active[i];
while (pi < ord && lef[V[pi]] >= L[qi])
sum += vt_up[V[pi++]];
Ans[qi] += sum;
}
/* mutex, ql > x and y <= qr */
rev(active, nactive);
rev(V, ord);
pi = 0;
for (int i = 0; i < nactive; ++i) {
int qi = active[i];
while (pi < ord && lef[V[pi]] < L[qi])
fw_add(rgt[V[pi]], vt_up[V[pi]]), ++pi;
Ans[qi] += fw_sum(R[qi]);
}
/* undo all fenwick upd (IM GONNA KILLL MYSELF AG IRUH */
pi = 0;
for (int i = 0; i < nactive; ++i) {
int qi = active[i];
while (pi < ord && lef[V[pi]] < L[qi])
fw_add(rgt[V[pi]], -vt_up[V[pi]]), ++pi;
}
free(V);
free(active);
dnc(l, m, left, nleft);
dnc(m + 1, r, right, nright);
free(left);
free(right);
}
int main() {
scanf("%d%d%d", &N, &M, &Q);
for (int i = 1, A, B; i < N; ++i)
scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
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 = (int*)malloc(sizeof*candidates * Q);
for (int i = 0; i < Q; ++i)
scanf("%d%d", L + i, R + i), --L[i], --R[i], candidates[i] = i;
dnc(0, M - 1, candidates, Q);
for (int i = 0; i < Q; ++i)
printf("%d\n", Ans[i] + 1);
free(candidates);
}
/*
* https://codeforces.com/blog/entry/114003?#comment-1015100
*
* DNC
*/
Compilation message
tourism.c: In function 'dnc':
tourism.c:168:34: warning: assignment to 'int' from 'void *' makes integer from pointer without a cast [-Wint-conversion]
168 | vtdeg[V[i]] = vtdeg2[V[i]] = NULL;
| ^
tourism.c:195:29: warning: initialization of 'int' from 'void *' makes integer from pointer without a cast [-Wint-conversion]
195 | *left = NULL, nleft = NULL,
| ^~~~
tourism.c: In function 'main':
tourism.c:256:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
256 | scanf("%d%d%d", &N, &M, &Q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.c:258:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
258 | scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
| ^~~~~~~~~~~~~~~~~~~~~
tourism.c:262:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
262 | scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
| ^~~~~~~~~~~~~~~~~~
tourism.c:265:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
265 | scanf("%d%d", L + i, R + i), --L[i], --R[i], candidates[i] = i;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
73 ms |
22936 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
