noip模拟赛蒜头君的树

#include 
#include 
#include 
#include 

using namespace std;

const int maxn = 100010;

long long n, head[maxn], nextt[maxn * 2], tot = 1, to[maxn * 2], w[maxn * 2], num[maxn], fa[maxn], d[maxn], m;
long long ans;

void add(long long x, long long y, long long z)
{
    to[tot] = y;
    w[tot] = z;
    nextt[tot] = head[x];
    head[x] = tot++;
}

void dfs(long long u, long long fa)
{
    for (int i = head[u]; i; i = nextt[i])
    {
        int v = to[i];
        if (v != fa)
        {
            dfs(v, u);
            num[u] += num[v];
            ans += w[i] * num[v] * (n - num[v]);
        }
    }
    num[u]++;
}

int main()
{
    scanf("%lld", &n);
    for (int i = 2; i <= n; i++)
    {
        long long x, y;
        scanf("%lld%lld", &x, &y);
        fa[i] = x;
        d[i] = y;
        add(x, i, y);
    }
    dfs(1, fa[1]);
    printf("%lld\n", ans);
    scanf("%lld", &m);
    for (int i = 1; i <= m; i++)
    {
        long long a, b;
        scanf("%lld%lld", &a, &b);
        ans += num[a] * (n - num[a]) * (b - d[a]);
        printf("%lld\n", ans);
        d[a] = b;
    }

    return 0;
}