牛客练习赛6B 点权和( Tree

点权和

题目描述

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

输入

第一行两个数n和m
第二行n-1个数，第i个数fa[i + 1]表示i + 1点的父亲编号，保证fa[i + 1]

输出

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

样例

输入
6 3
1 1 2 3 3
1 2 3
输出
34
示例2
输入
6 10
1 1 2 3 3
1 4 6 5 2 3 3 3 3 3
输出
869
备注:
n <= 100000
m <= 10000000

题意

O(m) O ( m ) 的更新， 输入量要加速

AC代码

#include <bits/stdc++.h>
using namespace std;
#define CLR(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define sf(i) scanf("%d",&i)
#define pf(i) printf("%dn",i)
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5+10;
const int mod = 19260817;
int
arr[MAXN], cnt[MAXN], sum[MAXN], fa[MAXN];
/*
arr 为节点x的权值
cnt 为x的出现次数
sum 为x所有子节点的权值
fa 为x的父节点
每次计算的点权和为 ans = sum[x]子节点+arr[x]+cnt[fa[x]]自身权值+arr[fa[x]]+cnt[fa[fa[x]]]父亲权值
*/
vector<int> G[MAXN];
long long read()
{
long long res = 0;
char ch = 0;
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9')
{
res = res * 10 + ch - '0';
ch = getchar();
}
return res;
}
int main()
{
int n, m, x;
sf(n); sf(m);
for(int i = 2; i <= n; i++) {
sf(x);
G[x].push_back(i);
fa[i] = x;
}
fa[1] = 0;
LL res = 0;
for(int i = 1; i <= m; i++) {
LL ans = 0; x = read();
arr[x]++, cnt[x]++;
sum[x] += int(G[x].size());
sum[x] %= mod;
arr[fa[x]]++;
sum[fa[x]]++, sum[fa[fa[x]]]++;
sum[0] = 0, cnt[0] = 0, arr[0] = 0;
ans = (sum[x]+arr[x]+cnt[fa[x]]+arr[fa[x]]+cnt[fa[fa[x]]])%mod;
res = (res+(LL)ans*i%mod)%mod;
}
return 0*printf("%lldn",res);
}

最后

以上就是完美柠檬为你收集整理的牛客练习赛6B 点权和( Tree的全部内容，希望文章能够帮你解决牛客练习赛6B 点权和( Tree所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。