【Nowcoder】点权和好骚的思维

57 阅读 0 评论 38 点赞

我是靠谱客的博主留胡子棒球，最近开发中收集的这篇文章主要介绍【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的所有孙子节点的的贡献

所以向下的贡献也就非常容易算了： $ftag[x]*2+gftag[x]$

2.考率向上的贡献：

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

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

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

所以向上的贡献为： $tag[fa[fa[x]]]+tag[fa[x]]*2+ftag[fa[x]]]-tag[x]$

3.最后考虑自己对所有邻接点的贡献 : $in[i]*tag[x]$

所以每次操作后的结果就是上述所有贡献之和，可以发现答案完全可以用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;///当前节点影响加1
        if(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("%lldn",(ans)%mod);
    return 0;
}

总结：

这么骚的操作一定要学！

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

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