自动搬运

查看原文

来自洛谷，原作者为

	cengzh 该用户未填写评价内容，已自动好评。

搬运于2025-08-24 23:07:42，当前版本为作者最后更新于2024-12-28 21:55:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

传送门

虽然重交了几次了，但真不是故意的，错误好难找，辛苦管理员了。

考虑将 $f(x)$ 转化为更好求得的形式。

记 $dep_p$ 为 $p$ 到根节点的距离，$v_p$ 为 $p$ 的点权。

对于节点 $x$，令其子树内所有点为 $a_1,a_2,$ $\dots$ $,a_n$。

于是有：

$$f(x) = v_{a_1} \times (dep_{a_1} - dep_x) + v_{a_2} \times (dep_{a_2} - dep_x) + \ldots + v_{a_n} \times (dep_{a_n} - dep_x) $$

将括号拆开，得：

$$f(x) = v_{a_1} \times dep_{a_1} + v_{a_2} \times dep_{a_2} + \ldots + v_{a_n} \times dep_{a_n} - \sum_{i=1}^n v_{a_i} \times dep_x $$

在这个式子中，有非常多的不变量，我们只用预处理三个量。

1. 深度 $dep_p$
2. 减号前这一串式子，记为 $tot_p$
3. $\sum_{i=1}^n v_{a_i}$，记为 $sum_p$（$p$ 子树内节点点权和）

即可求 $f(x)$。

现在回到查询，我们简要概括这个操作：

给出 $(x,y)$，将 $x$ 沿父亲不断上移成 $y$ 的儿子，$x$ 的所有儿子由 $x$ 的原父亲继承，求 $f(y)$。

我们尝试找到一些结论：

• 结论1：对于 $x$，其子树内所有节点产生的贡献不变。

  证明：对于 $x$ 子树内的每个节点，$x$ 上移后，深度仍不变，点权亦不变，那么贡献不变。

• 结论2：对于 $y$ 包含 $x$ 的子树的根节点 $y_{son}$，$x$ 上移后，整体贡献加 $(sum_{y_{son}} + v_{y_{son}}) -( sum_x + v_x)$。

  证明：记 $y$ 包含 $x$ 的子树内所有非 $x$ 子树内节点的节点为 $b_1,b_2 \ldots b_m$，对于 $i \in [1,m]$，容易证明 $x$ 上移后 $b_i$ 到 $y$ 的距离加 $1$，那么这部分的贡献就多了 $\sum_{i=1}^m v_{b_i}$。

  容易得：

  $$\sum_{i=1}^m v_{b_i} = (sum_{y_{son}} + v_{y_{son}}) -( sum_x + v_x) $$

有了这两个结论，结合 $x$ 上移对 $x$ 本身贡献的影响，求 $f'(y)$ 就很简单了。

$$f'(y) = f(y) + (sum_{y_{son}} + v_{y_{son}}) -( sum_x + v_x) + v_x - v_x \times (dep_x - dep_y) $$

整理得：

$$f'(y) = f(y) + sum_{y_{son}} + v_{y_{son}} - sum_x - v_x \times (dep_x - dep_y) $$

由数据范围想到要用 $O(n \log n)$ 时间复杂度的算法。

题目的优化关键在求 $y_{son}$，我们使用倍增法。

预处理 $O(n)$，查询 $O(q)$，每次查询 $O(\log n)$ 找子树。

总时间复杂度为 $O(n + q \log n)$。

以下为代码：

# include <stdio.h>
# include <stdlib.h>

struct Node
{
	int p;
	struct Node* next;
}; 

struct Head
{
	struct Node* next;
};

struct Head p[500005];
long long val[500005]; 
long long tot[500005];
long long dep[500005];
long long sum[500005];
long long f[500005];
int father[500005][22];
int cur;

struct Node* ini()
{
	struct Node* tmp = (struct Node*) malloc (sizeof(struct Node)); 
	tmp->next = NULL;
	return tmp;
}

void add(int u,int fa)
{
	struct Node* tmp = ini();
	tmp->p = u;
	tmp->next = p[fa].next;
	p[fa].next = tmp;
	return ;
}

void dfs(int u,int fa)
{
	dep[u] = dep[fa]+1;
	cur++;
	
	father[u][0] = fa;
	
	for (int i=1;i<21;i++)
	{
		father[u][i] = father[father[u][i-1]][i-1];
	}
	
	for (struct Node* tmp=p[u].next;tmp!=NULL;tmp=tmp->next)
	{
		int v = tmp->p;
		if (v == fa)
		{
			continue;
		}
		dfs(v,u);
		tot[u]+=tot[v]+val[v]*dep[v];
		sum[u]+=sum[v]+val[v]; 
	}
	f[u] = tot[u]-sum[u]*dep[u];

	return ;
}

int get_root(int x, int y)
{
    int k = 20;
    while (k >= 0)
    {
        if (dep[father[x][k]] >= dep[y]+1) 
    		{
            x = father[x][k];
        }
        k--;
    }
    return x;
}

int main (void)
{
	int n,q;
	scanf ("%d %d",&n,&q);
	
	for (int i=1;i<=n;i++)	
	{
		scanf ("%d",&val[i]);
		p[i].next = NULL;
	}
	
	for (int i=2;i<=n;i++)
	{
		int fa;
		scanf ("%d",&fa);
		add(i,fa);
	}
	
	dfs(1,1); 
	
	for (int i=1;i<=q;i++)
	{
		int x,y;
		scanf ("%d %d",&x,&y);
		int son = get_root(x,y);
		printf ("%lld\n",f[y]+sum[son]+val[son]-sum[x]-val[x]*(dep[x]-dep[y]));	//
	}
	
	return 0;
}