【NOIP模拟】蒜头君的树

题面

蒜头君有一棵有根树，树的每一边都有边权，蒜头君想知道任意两点间最短距离之和为多少。另外，由于各种原因，蒜头君的树的边的边权会发生若干次改变，蒜头君想让你告诉他，每一次改变后，任意两点间最短距离之和为多少？

数据规模：n<=1e5 m<=5000

分析

水题，统计以每个节点为根的子树的大小

修改一条边只影响这条边连的儿子节点的那一棵子树

ans+=siz[u]*(w2-w1)*(n-siz[u])。（w2为修改后的边权，w1为修改前，无修改的时候，w2==w,w1==0）

#include<bits/stdc++.h>
using namespace std;
#define N 100100
#define ll unsigned long long 
ll n,m,cnt,tot,ans;
ll first[N],siz[N],id[N];
struct email
{
    ll u,v,w;
    ll nxt;
}e[N*5];
inline void read(ll &x)
{
    x=0;char ch=getchar();
    while(ch>'9'||ch<'0'){ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
}

void dfs(ll u,ll fa)
{
    for(ll i=first[u];i;i=e[i].nxt)
    {
        ll v=e[i].v,w=e[i].w;
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}

inline void add(ll u,ll v,ll w)
{
    e[++cnt].nxt=first[u];first[u]=cnt;
    e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;
}
int main()
{
    read(n);
    for(ll i=1;i<=n;i++)
        siz[i]=1;
    for(ll v=2;v<=n;v++)
    {
        ll u,w;read(u);read(w);
        add(u,v,w);id[v]=cnt;add(v,u,w);
    }
    dfs(1,0);
    for(ll i=1;i<=cnt;i+=2)
    {
        ll u=e[i].v,w=e[i].w;
        ans+=siz[u]*w*(n-siz[u]);
    }
    printf("%lld
",ans);
    read(m);
    for(ll i=1;i<=m;i++)
    {
        ll u,w1,w2;
        read(u);read(w2);
        w1=e[id[u]].w;e[id[u]].w=w2;e[id[u]+1].w=w2;
        ans+=siz[u]*(w2-w1)*(n-siz[u]);
        printf("%lld
",ans);
    }
    return 0;
}