首先,考虑一下常规思路,每次将操作数和与操作数相连的点的权值都加一,然后计算值。显然这种思路的会TLE。不过我们可以发现,这种思路其实不止适用于树,还适用于图。如此我们便要思考,就本题而言,树与图有什么区别。
树型结构为一对多的关系,不像图的多对多,这使得我们可以从树中找到节点的祖宗及后代,因此我们要从这里入手。
先前常规思路的超时,主要原因是在每次操作中,计算了所有与操作数相连的点,时间复杂度为O(n),我们需要在O(1)的时间复杂度内完成此操作。在树型结构中,一次操作要计算指定点、其父节点和其所有子节点,而一次对指定点的操作会影响到其父节点、子节点和其祖父节点、孙子节点(当计算与其相邻的点权值时)。所以,若要在O(1)的时间内解决,我们除了要考虑直接关系,还要考虑隔代关系。
因此,记:
son[u]为该节点及其所有子节点的贡献(将该节点与子节点分开处理也可以);
father[u]为当该节点作为父节点时,对其子节点的贡献;
gfather[u]为当该节点作为祖父节点时,对其孙子节点的贡献;
cnt_son[u]为该节点的孩子数;
fa[u]为该节点的父亲节点。
当对节点u进行操作时,
son[u]+=cnt_son[u]+1;(该节点和其子节点权值均加一使得贡献如此增加);
father[u]+=2;(无法将所有子节点权值加一,只能将父节点对子节点的贡献加二);
gfather[u]++;(该节点通过使子节点的权值加一,使孙节点计数时,其对孙节点的贡献加一);
son[fa[u]]+=2;(该节点与父节点的权值均加一使得对父节点贡献如此增加);
father[fa[u]]++;(该节点父节点权值加一,父节点对子节点贡献加一);
son[fa[fa[u]]]++;(父节点权值加一,其对祖父节点的贡献加一);
记该操作对答案的贡献为tmp,
tmp=son[u]+father[fa[u]]+gfather[fa[fa[u]]];
则:ans=(ans+tmp*i)%mol;
值得注意的是,在以上操作中,并没有直接增加某个节点的权值,改变的只是一个点(或一些点)对另外一个点(或一些点)的贡献。
代码:
#include <iostream> #include <queue> #include <set> #include <map> #include <vector> #include <stack> #include <cmath> #include <algorithm> #include <cstdio> #include <cctype> #include <functional> #include <string> #include <cstring> #include <sstream> #include <deque> #define fir first #define sec second using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<P,int> Q; const int inf1=2e9+9; const ll inf2=8e18+9; const int mol=19260817;//1e9+7; const int maxn=1e5+9; const ll maxx=1e12+9; int n,m,fa[maxn]; ll father[maxn],gfather[maxn],son[maxn],cnt_son[maxn]; int main() { scanf("%d%d",&n,&m); for(int i=2;i<=n;i++) { int f; scanf("%d",&f); fa[i]=f; cnt_son[f]++; } int ans=0; for(int i=1;i<=m;i++) { int u; scanf("%d",&u); son[u]+=cnt_son[u]+1; father[u]+=2; gfather[u]+=1; ll tmp=son[u]; if(fa[u]) { son[fa[u]]+=2; father[fa[u]]++; tmp+=father[fa[u]]; if(fa[fa[u]]) { son[fa[fa[u]]]++; tmp+=gfather[fa[fa[u]]]; } } ans=(ans+tmp*i%mol)%mol; } printf("%d\n",ans); }