【每日一题】点权和
点权和
https://ac.nowcoder.com/acm/problem/14393
题意:
思路:
首先感谢 a^-^a 大佬,我是看了他的博客,思路和注释都很清晰
他的博客
#include <cstdio> using namespace std; typedef long long ll; const int N = 1e5 + 10; const int mod = 19260817; int n,m; ll now[N];//当前节点被操作的次数 ll son[N];//当前节点的儿子节点们被操作的次数 ll gson[N];//当前节点的孙子节点们被操作的次数 int fa[N],sz[N];//fa[u] = v,表示u的父节点为v,没有时为0;sz[i],节点i的儿子节点个数 int main(){ scanf("%d%d",&n,&m); for(int i = 1,u;i < n;i++){ scanf("%d",&u); fa[i + 1] = u; sz[u]++; } ll ans = 0; for(int i = 1,u;i <= m;i++){ scanf("%d",&u); now[u]++;//当前节点被操作了一次 if(fa[u]) son[fa[u]]++;//若当前节点有父节点,则告知它的父节点:你的儿子节点被操作了一次 if(fa[fa[u]]) gson[fa[fa[u]]]++;//若当前节点存在爷爷节点,则告知它的爷爷节点,你的孙子节点被操作了一次 //仅仅对节点u操作,影响的只有u本身,u的父节点以及u的儿子节点 //因此将对答案的贡献拆分为三部分: //1.父节点对答案的贡献 ll sum = (now[fa[u]] + son[fa[u]] + now[fa[fa[u]]]) % mod; //2.u本身 sum = ( sum + (now[u] + son[u] + now[fa[u]]) % mod ) % mod; //3.u的儿子节点们 sum = ( sum + (son[u] + gson[u] + sz[u]*now[u]%mod)%mod) % mod; ans = ( ans + (sum * i)%mod ) % mod; } printf("%lld\n",ans); return 0; }
每日一题 文章被收录于专栏
每题一题题目