Luogu P1600 [NOIP2016 improvement group] loves running every day
1, Rough analysis
There are hints in the data range that the tree may degenerate into a chain, so the simulation time complexity can reach \ (O(nm) \), which is obviously not acceptable.
Continuing to analyze the topic, it can be found that for a path from \ (s_i \) to \ (t_i \), it can be divided into \ (s_i \) and the nearest common ancestor \ (lca_i \) of \ (t_i \). For \ (k \) that meets the requirements at a certain point on it, there are:
If \ (K \) is in the uplink segment, then \ (deep_k + w_k = deep_{s_i} \)
If \ (K \) is in the downstream segment, \ (dist_{s_i}, {t_i} - w_k = deep_{t_i} - deep_k \), i.e. \ (dist_{s_i}, {t_i} - deep_{t_i} = w_k - deep_k \)
In addition to the above two formulas, it is also noted that the starting point and ending point of the path that can contribute to \ (k \) must be on the subtree with \ (k \) as the root, so two arrays can be opened, recorded in the left side of the above formula when traversing depth first, and counted in the right side.
However, it should be noted here that the number of times \ (k \) is passed is not a downward recursion directly through the array query, but the difference between the value after recursion and the value before entering the subtree.
2, Code & some details
1. Input:
Ordinary read in, no special code.
2. Request LCA:
int fa[MAXN], siz[MAXN], son[MAXN], dep[MAXN] = {0}, top[MAXN];
void setup(int x, int fat)
{
fa[x] = fat;
siz[x] = 1, son[x] = -1;
dep[x] = dep[fat] + 1;
for (int i = head[x]; ~i; i = e[i].nxt)
{
int y = e[i].to;
if (y == fat)
continue;
setup(y, x);
siz[x] += siz[y];
if (son[x] == -1 || siz[son[x]] < siz[y])
son[x] = y;
}
}
void cut(int x, int t)
{
top[x] = t;
if (son[x] == -1)
return ;
cut(son[x], t);
for (int i = head[x]; ~i; i = e[i].nxt)
{
int y = e[i].to;
if (y != fa[x] && y != son[x])
cut(y, y);
}
}
int getLca(int x, int y)
{
while (top[x] != top[y])
{
if (dep[top[x]] > dep[top[y]])
x = fa[top[x]];
else
y = fa[top[y]];
}
return (dep[x] < dep[y]) ? x : y;
}
Compare the tree section of the template to calculate the LCA (do not want to open the two-dimensional array to write multiplication, and others will not). I won't explain it.
3. Pretreatment
void add1(int x, int y)
{
e1[++tot1].to = y;
e1[tot1].nxt = head1[x];
head1[x] = tot1;
}
void add2(int x, int y)
{
e2[++tot2].to = y;
e2[tot2].nxt = head2[x];
head2[x] = tot2;
}
int main()
{
input();
setup(1, 0);
cut(1, 1);
for (int i = 1; i <= m; i++)
{
int lca = getLca(s[i], t[i]);
dist[i] = dep[s[i]] + dep[t[i]] - 2 * dep[lca];
st[s[i]]++;
add1(t[i], i);
add2(lca, i);
if (dep[lca] + w[lca] == dep[s[i]])
ans[lca]--;
}
return 0;
}
\(dist_i \): the length of the i-th path
\(st_i \): the number of paths starting from I
\(add1 \): a collection of paths starting with i stored in a chained forward star
\(add2 \): a set of chained forward stars that store the paths of the nearest common ancestor starting from and ending at i
It should be noted that if the starting point or end point of the path coincides with the LCA and meets the requirements here, it will be counted twice, so it will be subtracted in advance.
if (dep[lca] + w[lca] == dep[s[i]]) ans[lca]--;
4. The last deep search for statistical answers
int bu1[MAXN * 2], bu2[MAXN * 2];
void dfs(int x)
{
int t1 = bu1[w[x] + dep[x]], t2 = bu2[w[x] - dep[x] + MAXN];//Record the array state before entering the subtree
for (int i = head[x]; ~i; i = e[i].nxt)
{
int y = e[i].to;
if (y != fa[x])
dfs(y);
}
bu1[dep[x]] += st[x];//Uplink segment answer
for (int i = head1[x]; ~i; i = e1[i].nxt)//Downlink answer
{
int y = e1[i].to;
bu2[dist[y] - dep[t[y]] + MAXN]++;
}
ans[x] += bu1[w[x] + dep[x]] - t1 + bu2[w[x] - dep[x] + MAXN] - t2;//Statistical answer
for (int i = head2[x]; ~i; i = e2[i].nxt)//A path with the current x as the LCA will not contribute to its ancestor nodes and sibling nodes
{
int y = e2[i].to;
bu1[dep[s[y]]]--;
bu2[dist[y] - dep[t[y]] + MAXN]--;
}
}
\(bu1 \): used to store the contribution of uplink segments
\(bu2 \): used to store the contribution of downlink segments, \ (dist_{s_i}, {t_i} - deep_{t_i} \) may be less than \ (0 \), so \ (MAXN \) is added.
5. Output:
There's nothing to say.
6. Final personal code:
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 3e5;
struct Edge
{
int to, nxt;
} e[MAXN * 2], e1[MAXN], e2[MAXN];
int n, m, w[MAXN], s[MAXN], t[MAXN], tot = -1, head[MAXN];
int fa[MAXN], siz[MAXN], son[MAXN], dep[MAXN] = {0};
int dfn[MAXN], rnk[MAXN], top[MAXN], cnt = 0;
int dist[MAXN], st[MAXN] = {0}, ans[MAXN] = {0};
int tot1 = -1, tot2 = -1, head1[MAXN], head2[MAXN];
int bu1[MAXN * 2], bu2[MAXN * 2];
void add(int x, int y)
{
e[++tot].to = y;
e[tot].nxt = head[x];
head[x] = tot;
}
void add1(int x, int y)
{
e1[++tot1].to = y;
e1[tot1].nxt = head1[x];
head1[x] = tot1;
}
void add2(int x, int y)
{
e2[++tot2].to = y;
e2[tot2].nxt = head2[x];
head2[x] = tot2;
}
void input()
{
memset(head, -1, sizeof(head));
memset(head1, -1, sizeof(head1));
memset(head2, -1, sizeof(head2));
scanf("%d %d", &n, &m);
for (int i = 1; i < n; i++)
{
int x, y;
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
for (int i = 1; i <= n; i++)
scanf("%d", w + i);
for (int i = 1; i <= m; i++)
scanf("%d %d", s + i, t + i);
}
void setup(int x, int fat)
{
fa[x] = fat;
siz[x] = 1, son[x] = -1;
dep[x] = dep[fat] + 1;
for (int i = head[x]; ~i; i = e[i].nxt)
{
int y = e[i].to;
if (y == fat)
continue;
setup(y, x);
siz[x] += siz[y];
if (son[x] == -1 || siz[son[x]] < siz[y])
son[x] = y;
}
}
void cut(int x, int t)
{
top[x] = t;
dfn[x] = ++cnt;
rnk[dfn[x]] = x;
if (son[x] == -1)
return ;
cut(son[x], t);
for (int i = head[x]; ~i; i = e[i].nxt)
{
int y = e[i].to;
if (y != fa[x] && y != son[x])
cut(y, y);
}
}
int getLca(int x, int y)
{
while (top[x] != top[y])
{
if (dep[top[x]] > dep[top[y]])
x = fa[top[x]];
else
y = fa[top[y]];
}
return (dep[x] < dep[y]) ? x : y;
}
void dfs(int x)
{
int t1 = bu1[w[x] + dep[x]], t2 = bu2[w[x] - dep[x] + MAXN];
for (int i = head[x]; ~i; i = e[i].nxt)
{
int y = e[i].to;
if (y != fa[x])
dfs(y);
}
bu1[dep[x]] += st[x];
for (int i = head1[x]; ~i; i = e1[i].nxt)
{
int y = e1[i].to;
bu2[dist[y] - dep[t[y]] + MAXN]++;
}
ans[x] += bu1[w[x] + dep[x]] - t1 + bu2[w[x] - dep[x] + MAXN] - t2;
for (int i = head2[x]; ~i; i = e2[i].nxt)
{
int y = e2[i].to;
bu1[dep[s[y]]]--;
bu2[dist[y] - dep[t[y]] + MAXN]--;
}
}
int main()
{
input();
setup(1, 0);
cut(1, 1);
for (int i = 1; i <= m; i++)
{
int lca = getLca(s[i], t[i]);
dist[i] = dep[s[i]] + dep[t[i]] - 2 * dep[lca];
st[s[i]]++;
add1(t[i], i);
add2(lca, i);
if (dep[lca] + w[lca] == dep[s[i]])
ans[lca]--;
}
dfs(1);
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
printf("\n");
return 0;
}