点权和_牛客博客

题目描述

给你一棵树，最开始点权为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取模的结果

题解

对于本题，数据范围太大，没办法进行暴力，我们考虑谁对当前点有贡献。

对于一个点，对他有贡献的点就是他自己，他的父亲和他的儿子。

对于他自己和他父亲的贡献，我们很好维护。对于自己，我们维护一个 $cnt[i]$ 数组，表示i点被操作的个数；对于父亲，我们维护一个 $fa[i]$ 数组，表示i结点的父亲，那对于某节点父亲的贡献就是 $cnt[fa[i]]$ 。

比较棘手的是维护儿子。我们没办法直观的得到儿子节点的编号，那我们换一种方式，维护一个 $son[i]$ 数组，表示父亲节点为i的节点被操作的次数。在我们每得到一个要被操作的节点 $x$ 时，我们只需要对 $son[fa[x]]$ 进行加一就可以轻松的维护儿子信息。

假设我们现在要做操作的是节点 $x$ ，那么x的父亲节点的权值为 $father=cnt[fa[x]]+cnt[fa[fa[x]]+son[fa[x]]$ ，其中 $cnt[fa[x]]$ 表示x父节点被操作的次数， $cnt[fa[fa[x]]$ 表示x父节点的父节点被操作的次数， $son[fa[x]]$ 表示以x的父节点为父节点的儿子被操作的次数。

那么x本身的权值同理，为 $itself=cnt[x]+cnt[fa[x]]+son[x]$ ，其中 $cnt[x]$ 表示x被操作的次数， $cnt[fa[x]]$ 表示x父节点被操作的次数， $son[x]$ 表示以x为父节点的儿子被操作的次数。

对于x的儿子，比较棘手。其一因为我们没办法获得x儿子的儿子，我们仿照之前的解决方法，再维护一个 $gson[i]$ 数组，表示以i为爷爷的结点被操作的次数，同理，在我们每得到一个要被操作的节点 $x$ 时，我们只需要对 $gson[fa[fa[x]]]$ 进行加一就可以维护孙子信息。其二是因为此时x的儿子不只是一个，所以其父亲对于他的贡献不再单单是被操作次数，而应该还要乘上此时儿子的数量，这个问题很好解决，我们只需要设置一个siz数组，在输入父节点时同时维护了fa数组和siz数组就可以啦。

那么现在我们就可以算x的儿子的权值了， $son=cnt[x]*siz[x]+son[x]+gson[x]$ ，其中 $cnt[x]*siz[x]$ 表示x对他儿子的贡献， $son[x]$ 表示以x的儿子被操作的次数， $gson[x]$ 表示x的儿子节点的儿子节点被操作的次数。

所以操作x之后的被修改的节点的权值和就是father+itself+son了，然后我们按照题干的要求计算hash值就好啦

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=1e5+100;
int fa[N];
ll it[N],son[N],gson[N],siz[N];
const int mod=19260817;
int n,m;
////////////////////////////////////////////////////////////////////////
int main(){
    n=gn(),m=gn();
    for(int i=2;i<=n;++i){
        fa[i]=gn();
        siz[fa[i]]++;
    }
    ll ans=0;
    for(int cnt=1;cnt<=m;++cnt){
        int i=gn();
        ++it[i];
        if(fa[i])++son[fa[i]];
        if(fa[fa[i]])++gson[fa[fa[i]]];
        ll d=0;
        d=(d+(it[fa[i]]+it[fa[fa[i]]]+son[fa[i]])%mod)%mod;
        d=(d+(it[i]+it[fa[i]]+son[i])%mod)%mod;
        d=(d+(siz[i]%mod*it[i]%mod+son[i]+gson[i])%mod)%mod;
        ans=(ans+d*cnt%mod)%mod;
    }
    print(ans%mod);
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/