【每日一题】 点权和

首先，考虑一下常规思路，每次将操作数和与操作数相连的点的权值都加一，然后计算值。显然这种思路的会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);
}