【Nowcoder】点权和 好骚的思维

链接：https://ac.nowcoder.com/acm/problem/14393
来源：牛客网
 

题目描述

给你一棵树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和.

输入描述:

第一行两个数n和m
第二行n-1个数，第i个数fa[i + 1]表示i + 1点的父亲编号，保证fa[i + 1]<i + 1
第三行m个数，每个数x依次表示这次操作的点是x

输出描述:

输出一个数，即这m次操作的答案的hash值
如果是第i次操作，这次操作结果为ans,则这个hash值加上
i * ans
输出hash值对19260817取模的结果

题解：

我试图去遍历邻接表（以为是水题），结果T飞了呀——m1e7，随便出点数据就可以卡了。

看一下正解：

用一个数组表示，当前这个点操作了几次，那么就如上图所示，绿色的点操作x次对此次操作的贡献即为2*x，蓝色的点为1*x。

很显然x的操作次数的贡献为：x的度数+1。

所以显然需要维护邻接点，但是这个邻接点不太好维护，考虑树的性质:一个点的父亲节点有且只有一个。

那么就想到维护 父亲节点。

首先解释一下下面所用到的所有数组：

tag[x] ，x节点被操作了几次

ftag[x]，x节点作为被操作节点的父节点的次数

gftag[x]，x节点作为被操做节点爷爷节点的次数

设tag[i]表示第i个节点操作了多少次,那么我们把问题分解开，也就是一个节点向下的贡献(儿子及孙子)与向上的贡献之和(父亲及爷爷)最后再加上这个点的贡献。

1.考虑向下的贡献：

怎么知道x有几个儿子节点呢被操作了呢，因为树的父亲节点只有一个，所以可以在对儿子进行操作时，用一个数组ftag[i]辅助，ftag[i]表示i作为父节点一共被操作了多少次，反过来也就是说ftag[i]表示i节点的所有儿子的贡献。

例如对x点进行操作那么:ftag[fa[x]]++

同理，当对孙子进行操作时考虑爷爷的贡献。gftag[i]表示i的所有孙子节点的的贡献

所以向下的贡献也就非常容易算了：

2.考率向上的贡献：

因为父亲只有一个：那么答案首先要加上tag[fa[x]]，表示父亲被操作了多少次。

接下来就是爷爷的贡献：tag[fa[fa[x]]]

但是这时候注意，向上的贡献没有考虑完全：可能一个点y是x的兄弟节点，如果y被操作了的话，x的父亲节点也会被更新，也就是说父亲节点作为父亲节点的时候也有1的贡献。所以答案还需要加上ftag[fa[x]]但是此时父亲节点作为父亲节点时候的贡献包含作为x节点父亲的贡献，而不完全是兄弟节点的。所以ftag[fa[x]]-tag[x]是父亲作为兄弟节点的贡献。

所以向上的贡献为：

3.最后考虑自己对所有邻接点的贡献 :

所以每次操作后的结果就是 上述所有贡献之和，可以发现答案完全可以用Om的复杂度去维护

代码：

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const ll INF=1e18;
const int maxn=5e5+18;
const int mod=19260817;
inline bool read(ll &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
ll tag[maxn];
ll ftag[maxn];
ll gftag[maxn];
int fa[maxn];
ll in[maxn];
int main()
{read(n);read(m);for(int i=2;i<=n;i++){int x;scanf("%d",&x);fa[i]=x;in[i]++;in[x]++;}ll ans=0;for(int i=1;i<=m;i++){int x;scanf("%d",&x);ll temp=0;tag[x]=(tag[x]+1)%mod;///当前节点影响加1if(fa[x]){///存在父亲节点 该父亲节点被儿子节点影响了一次ftag[fa[x]]=(ftag[fa[x]]+1)%mod;///fa[x]作为父节点的次数++temp=(temp+tag[fa[x]]*2+(ftag[fa[x]]-tag[x]))%mod;///父亲节点被操作的次数 对答案的贡献为*2}if(fa[fa[x]]){///存在爷爷节点gftag[fa[fa[x]]]=(gftag[fa[fa[x]]]+1)%mod;temp=(temp+tag[fa[fa[x]]])%mod;///爷爷节点对该点的影响为1}temp=(temp+(in[x]+1)*tag[x]+ftag[x]*2+gftag[x])%mod;ans=(ans+i*temp%mod)%mod;}printf("%lld\n",(ans)%mod);return 0;
}

总结：

这么骚的操作一定要学！

1.树上操作距离小于等于1时的贡献直接考虑父亲节点 儿子节点 孙子节点 爷爷节点 及兄弟节点的贡献即可，并且将儿子与孙子节点的贡献压缩。

2.如果每次操作不+1，而是改成+x,其实道理都一样，不过把上述+1的题目都改为+x即可。