感谢sunsetcolors大佬的博客,提供思路
首先题意需要仔细看,大致就是,给你一棵树,开始每个点权都是0,m次操作,每次操作会把这个点在树上距离小于等于1的点权都加1. 并且把这个点权和距离小于等于1的点权都加起来为k, ans=k*i。 i表示每次操作的编号
分析: 由于m=1000000很大。建树暴力加是妥妥TLE了。本人亲测只能对30。
那么这题的突破口就是树上距离小于等于1的点,可以从每个点影响周围点的贡献入手。 一个点无非就是影响他的儿子,他的父亲,他自己。
所以只要把 这个点父亲节点的贡献+这个点儿子节点的贡献+这个点本身的贡献 就完事了
定义数组 now[x] 表示节点x被操作的次数
son[x] 表示节点x的儿子被操作的次数
b[x] 表示节点x的孙子被操作的次数 为什么要孙子,因为在处理儿子节点的贡献时,孙子节点对儿子节点会产生影响的。
具体细节在代码注释里
AC代码:
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> #include <queue> #include <deque> #include <set> #include <stack> #include <cctype> #include <cmath> #include <cassert> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define INF 0x3f3f3f3f #define PI 3.14159265358979323846 using namespace std; typedef long long ll; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } const ll MOD=19260817; const int N=100000+100; int n,m,x; ll now[N];//表示当前节点被操作的次数 ll son[N];//表示儿子节点被操作的次数 ll b[N]; //表示孙子节点被操作的次数 ll fa[N]; //表示当前节点的父亲节点是谁 int siz[N];//表示当前节点儿子的数量 int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { scanf("%d",&x); fa[i+1]=x; siz[x]++; } ll ans=0; for(int i=1;i<=m;i++) { scanf("%d",&x); ll k=0; now[x]++;//当前节点x被操作了一次 if(fa[x]!=0)son[fa[x]]++;//如果当前节点的父亲存在,那么这个父亲节点的儿子操作次数++ if(fa[fa[x]]!=0)b[fa[fa[x]]]++;//如果当前节点父亲的父亲存在,说明当前节点是fa[fa[x]]的孙子节点,那么孙子节点也要++ //处理父亲节点的贡献 k=k+now[fa[x]]%MOD+son[fa[x]]%MOD+now[fa[fa[x]]]%MOD; //父亲节点自己被操作的次数now[fa[x]] // 父亲节点儿子被操作的次数son[fa[x]] //父亲节点的父亲节点自己被操作的次数now[fa[fa[x]]] k%=MOD; //处理自己节点的贡献 k=k+now[x]%MOD+son[x]%MOD+now[fa[x]]%MOD; //自己节点本身被操作的次数now[x] //自己节点儿子被操作的次数son[x] //自己节点的父亲被操作的次数now[fa[x]] k%=MOD; //处理儿子节点的贡献 k=k+(siz[x]*now[x])%MOD+son[x]%MOD+b[x]%MOD; //当前节点操作一次,儿子节点对应也要操作, 儿子节点总贡献 siz[x]*now[x] k%=MOD; ans+=(k*i)%MOD; ans%=MOD; } printf("%lld\n",ans%MOD); return 0; }