企业网站备案时间,网站地图样式,php网站开发视频教学,新手seo要学多久来源#xff1a;牛客网#xff1a;
时间限制#xff1a;C/C 2秒#xff0c;其他语言4秒
空间限制#xff1a;C/C 131072K#xff0c;其他语言262144K
64bit IO Format: %lld题目描述
给你一棵树#xff0c;最开始点权为0#xff0c;每次将与一个点x树上距离1的所…来源牛客网
时间限制C/C 2秒其他语言4秒
空间限制C/C 131072K其他语言262144K
64bit IO Format: %lld题目描述
给你一棵树最开始点权为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取模的结果 示例1 输入 复制
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
题解
吐槽一下题意说的不明确搞的我一阵子以为自己读错了 hash值i*ans而ans等于点权1后与点x树上距离1的所有点权和 样例中最后答案就是3 * 15 * 27 * 334 根据题意当影响一个点x后x本身x的父亲x的儿子都会受到影响 int fa[x];//父亲节点 int now[x],son[x],grandson[x];//分别表示当前点被操作次数当前点的孩子节点操作次数当前点的孙子节点操作次数 int kid[x];//x的儿子节点有多少个
为啥要用当前点的儿子和孙子节点我是这么理解的因为每个点的父亲节点是唯一的一旦确定点x其父亲节点祖父节点都可以确定而一个点有未知个儿子节点所以用kid来记录儿子节点的数量。
最后计算x的贡献其实是x本身x的父亲x的儿子三个贡献和 x的父亲now[fa[x]]son[fa[x]]now[fa[fa[x]]] x的父亲节点的点权受x的父亲节点本身x节点以及x的父亲的父亲节点 x本身now[fa[x]]now[x]son[x] x的孩子kid[x]*now[x]son[x]grandson[x]
代码
代码只过了70%我也没找到哪里错了愁。。
#includeiostream
#includecstdio
#includecmath
#includealgorithm
#includecstring
#define maxn 10000008
const int mod19260817;
typedef long long ll;
using namespace std;
int fa[maxn];
int now[maxn],son[maxn],grandson[maxn];
int kid[maxn];
int main(){int n,m;cinnm;for(int i2;in;i){int x;cinx;fa[i]x;kid[x];}ll sum0;for(int i1;im;i){int x;cinx;now[x](now[x]1)%mod;if(fa[x])son[fa[x]];if(fa[fa[x]])grandson[fa[fa[x]]];int f(now[fa[x]]son[fa[x]]now[fa[fa[x]]])%mod;int m(now[fa[x]]now[x]son[x])%mod;int s(kid[x]*now[x]%modson[x]grandson[x])%mod;ll ans(fms)%mod;sum(sumans*i)%mod;} coutsum%mod;return 0;
}
