算是NOIP中比较麻烦的题了,看题解感觉处理的很巧妙
题意就不再赘述了,刚开始的想法是遍历枚举每一条路径,但是无论如何这样做的复杂度最坏都有O(nm)
所以尝试换一种方法,从观察员下手,对于每一个观察员,我们只需要找到每一条路径带给他的贡献
那这个贡献怎么求呢?
对于每一条路径(u,v),我们都可以将它拆为 u->lca 与 lca ->v
假设观察员的位置p在 u-> lca 上,当depth[u]+w[p]=depth[p]时才会有贡献
而当p在 lca->v 上时,只有dist(u,v)-(depth[v]-depth[p])=w[p],即dist(u,v)-depth[v]=w[p]-depth[p]时才有贡献
然后是统计贡献,如果我们在统计贡献时也一个一个去计算,那么复杂度就又上去了,所以这个时候可以用一个桶来处理,
这也是这道题比较巧妙的一点,
先看u->lca,对于点x,我们将它贡献的答案存在cnt[depth[x]]里,对于这条路径上的点p,更新答案就只需要加上cnt[depth[p]+w[p]]
对于lca->v,我们就将答案贡献存在cnt[dist(u,v)-depth[v]]里,同理对于p,更新答案加上cnt[w[p]-depth[p]]
然后是这道题中的一些细节部分,结合代码理解
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 3e5 + 5;
int cnt[N], ans[N], dist[N],t1[2 * N];
int w[N], s[N], t[N], fa[N][21], dep[N], t2[2 * N];
int head[N], ver[2 * N], net[2 * N], idx;
int head1[N], ver1[2 * N], net1[2 * N], idx1;
int head2[N], ver2[2 * N], net2[2 * N], idx2;
void add(int a, int b)
{
net[++idx] = head[a], ver[idx] = b, head[a] = idx;
}
void add1(int a, int b)
{
net1[++idx1] = head1[a], ver1[idx1] = b, head1[a] = idx1;
}
void add2(int a, int b)
{
net2[++idx2] = head2[a], ver2[idx2] = b, head2[a] = idx2;
}
void dfs1(int u, int f)
{
fa[u][0] = f, dep[u] = dep[f] + 1;
for (int i = 1; i <= 20; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int i = head[u]; i; i = net[i])
{
int v = ver[i];
if (v == f)
continue;
dfs1(v, u);
}
}
int lca(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
for (int i = 20; i >= 0; i--)
if (dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if (u == v)
return u;
for (int i = 20; i >= 0; i--)
if (fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}//求lca的部分,不作讲解
void dfs2(int u)
{
int tp1 = t1[dep[u] + w[u]], tp2 = t2[w[u] - dep[u] + N];//先存下来,接下来有用
for (int i = head[u]; i; i = net[i])
{
int v = ver[i];
if (v == fa[u][0])
continue;
dfs2(v);
}
t1[dep[u]] += cnt[u];
for (int i = head1[u]; i; i = net1[i])
{
int v = ver1[i];
t2[dist[v] - dep[t[v]] + N]++;
}//更新贡献
ans[u] += t1[dep[u] + w[u]] - tp1 + t2[w[u] - dep[u] + N] - tp2;
//tp1,tp2是之前计算的贡献,对于一条路径,只有带给以该路径的lca为根的子树内的点贡献,所以减去之前已经没有用的贡献
for (int i = head2[u]; i; i = net2[i])
{
int v = ver2[i];
t1[dep[s[v]]]--, t2[dist[v] - dep[t[v]] + N]--;//这个点没用了,将贡献减去
}
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
for (int i = 1; i <= n; i++)
scanf("%d", &w[i]);
dfs1(1, 0);
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &s[i], &t[i]);
int u = lca(s[i], t[i]);
dist[i] = dep[s[i]] + dep[t[i]] - 2 * dep[u];//计算路径长度
cnt[s[i]]++;//统计每个结点作为起点的路径条数
add1(t[i], i);//建立一个终点与路径的图
add2(u, i);//建立一个lca与路径的图
if (dep[u] + w[u] == dep[s[i]])//这里说一下,这种情况是u,v是一条链的情况,这种情况u->lca与lca->v会重复计算答案,所以减一
ans[u]--;
}
dfs2(1);
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}