这次考试后面心态爆炸了。。。发现刚了2h的T2是假的之后就扔掉了，草率地打了个骗分
T1只会搜索和m=0
最先做的T3，主要是发现部分分很多，当时第一眼看上去有87分（眼瞎了）。
后来想了想，感觉一条链不可做，69分
码出来69分之后去测了一下第二个大样例，发现跑了2.6s，心态爆炸，预计得分47
出分之后发现把4000的22分拿到了，有69分。
于是成功凭借T3苟进rk3
T1.
是个容斥好题，考场上一直在想如何对点容斥，想到考试结束也没想出来。
正解是容斥边。
T2.
欧拉回路
T3.
考试时用了0.5h切掉69分，想说一下，和正解思路完全不一样。
脸哥和正解都是将整体的式子化简求解，其实这个式子就是树上任意两点距离平方之和，因此我们可以考虑每个点对于答案的贡献。
考虑树上dp，如何从儿子的答案转移到父亲
我们令al[i]表示子树中所有点到i的距离之和，ans[i]表示子树中所有点到i的距离平方之和，siz[i]表示子树大小,w[i]表示i到父亲的距离。
那么有
ans[fa]+=ans[i]+2*al[i]*w[i]+w[i]*w[i]*siz[y]
al[fa]+=al[i]+siz[i]*w[i]
于是我们就可以求出来ans[1],然后我们可以通过上面这个式子进行换根，于是我们可以在O（n）的复杂度内求出解
总复杂度O（nq）,常数较大，代码实现很简单。
1 #include<bits/stdc++.h>
2 #define mod 1000000007
3 #define ll long long
4 using namespace std;
5 inline ll read(){
6 int x=0;
7 char ch=getchar();
8 while(ch<'0'||ch>'9')ch=getchar();
9 while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-48,ch=getchar();
10 return x;
11 }
12 int n,f[100005],fi[100005],to[100005],ne[100005],tot,sb,q;
13 ll siz[100005],al[100005],fang[100005],ans,ni,w[100005];
14 inline void add(int x,int y){
15 ne[++tot]=fi[x];
16 fi[x]=tot;
17 to[tot]=y;
18 }
19 void dfs(int x){
20 siz[x]=1;al[x]=0,fang[x]=0;
21 for(int i=fi[x];i;i=ne[i]){
22 int y=to[i];
23 dfs(y);
24 al[x]=(al[x]+al[y]+(siz[y]*w[y]))%mod;
25 fang[x]=(fang[x]+fang[y]+al[y]*w[y]*2+w[y]*w[y]%mod*siz[y])%mod;
26 siz[x]+=siz[y];
27 }
28 }
29 void dfs2(int x){
30 ans=(ans+fang[x])%mod;
31 for(int i=fi[x];i;i=ne[i]){
32 int y=to[i];
33 ll fx=(fang[x]-fang[y]-al[y]*w[y]*2-w[y]*w[y]%mod*siz[y])%mod,
34 ax=(al[x]-al[y]-(siz[y]*w[y]))%mod;
35 fang[y]=(fang[y]+fx+ax*w[y]*2+w[y]*w[y]%mod*(n-siz[y]))%mod;
36 al[y]=(al[y]+ax+(n-siz[y])*w[y])%mod;
37 dfs2(y);
38 }
39 }
40 int main(){
41 sb=read(),n=read(),q=read();
42 ni=50000004;
43 for(int i=2;i<=n;i++)f[i]=read(),w[i]=read(),add(f[i],i);
44 dfs(1);
45 dfs2(1);
46 printf("%lld\n",(ans+mod)%mod*ni%mod);
47 while(q--){
48 int u=read();
49 ll ad=read();
50 w[u]=(w[u]+ad)%mod;
51 dfs(1);
52 ans=0;
53 dfs2(1);
54 printf("%lld\n",(ans+mod)%mod*ni%mod);
55 }
56 return 0;
57 }
View Code
正解不会，咕了