A. Lighthouse

很明显的容斥题，组合式与上上场 \(t2\) 一模一样

注意判环时长度为 \(n\) 的环是合法的

---

B. Miner

题意实际上是要求偶拉路

对于一个有多个奇数点的联通块，直接 \(dfs\) 是不对的，可能搜索是来的不是一条路径

可以把个数大于 \(2\) 的联通块先强制奇数点两两连边，再跑两个奇数点的偶拉路

直接跑会 \(t\)，可以加入类似当前弧优化，注意每次 \(dfs\) 回溯时也要更新边为当前弧

void dfs(int u){
    for(int i=hd[u];i;){
        hd[u]=edge[i].nxt;
        if(!vis[i>>1]){
            int v=edge[i].to;
            deg[u]--;
            deg[v]--;
            vis[i>>1]=true;
            dfs(v);
            sta1[++tp1]=make_pair(edge[i].val,v);
            i=hd[u];
        }
        else i=edge[i].nxt;
    }
    return ;
}

---

C. Lyk Love painting

这 \(m\) 幅画居然不能重叠……

首先肯定二分，然后 \(dp\) 验证

设 \(f[i][j]\) 表示第一行选到第 \(i\) 列总共选了 \(j\) 幅画第二行最远选到第几幅画

转移需要双指针预处理第一行，第二行，以及两行从每一列出发最远能到达的距离

---

D. Revive

先把平方拆开，分为两部分：

• 对于每条边，其平方计算了经过这条边的路径数次，为 \(siz_u(n-siz_u)\)

• 对于每两条边，其乘机的二倍计算了同时经过这两条边的路径次数

  可以分三类讨论：

• \(v\) 在 \(u\) 子树内，为 \(2(n-siz[u]) * val[u] * siz[v] * val[v]\)

• \(v\) 在 \(u\) 到根节点路径上，为 \(2siz[u] * val[u] * (n-siz[v]) * val[v]\)

• \(v\) 和 \(u\) 的 \(lca\) 不是两点中的任意一个，为 \(2siz[u] * val[u] * siz[v] * val[v]\)

发现和 \(v\) 有关的式子都是 \(siz[v] * val[v]\)，那么用线段树维护这个值即可

由于需要维护到根节点路径的值，可以另开一棵记录每个点到根节点的前缀和，这样转化成每次区间修改单点查询，避免了多次跳链的 \(log\)

子树内权值和可以用树状数组维护以卡常

代码实现

#include<bits/stdc++.h>
using namespace std;
#define in long long
#define int long long
const int maxn=1e5+5;
const int maxm=1e5+5;
const int mod=1e9+7;
const int stan=1e15;
in n,m,fa[maxn],x,siz[maxn],re[maxn],dfn[maxn],hd[maxn],cnt,num;
int ans,w,val[maxn],sum[maxn],sum1[maxn],sumtot,c[maxn];
in read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
struct Edge{
    in nxt,to;
}edge[maxm];
void add(in u,in v){
    edge[++cnt].nxt=hd[u];
    edge[cnt].to=v;
    hd[u]=cnt;
    return ;
}
void change1(int x,int w){
    for(;x<=n;x+=x&-x)c[x]=(c[x]+w)%mod;
    return ;
}
int ask3(int x){
    int ans=0;
    for(;x;x-=x&-x)ans=(ans+c[x])%mod;
    return ans;
}
void modadd(int &x,int y){
    x=(x+y)%mod;
    if(x<0)x=(x+mod)%mod;
}
void dfs(in u){
    siz[u]=1;
    for(in i=hd[u];i;i=edge[i].nxt){
        in v=edge[i].to;
        dfs(v);
        siz[u]+=siz[v];
    }
    return ;
}
void dfs1(in u){
    sum[u]=(sum[fa[u]]+siz[u]*val[u]%mod)%mod;
    sum1[u]=(sum1[fa[u]]+val[u])%mod;
//    cout<<"ppp "<<sum1[u]<<endl;
    dfn[u]=++num;
    re[num]=u;
    for(in i=hd[u];i;i=edge[i].nxt){
        in v=edge[i].to;
        dfs1(v);
    }
    return ;
}
struct Seg{
    in l,r;
    int sum,lazy,sum1,lazy1,sum2,lazy2;
}t[maxn*4];
void update(in p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
    t[p].sum1=t[p<<1].sum1+t[p<<1|1].sum1;
//    if(t[p].sum>stan)t[p].sum%=mod;
//    if(t[p].sum1>stan)t[p].sum1%=mod;
//    t[p].sum2=t[p<<1].sum2+t[p<<1|1].sum2;
    return ;
}
void build(in p,in l,in r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].sum=sum[re[l]];
        t[p].sum1=sum1[re[l]];
//        t[p].sum2=siz[re[l]]*val[re[l]]%mod;
        return ;
    }
    in mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    update(p);
    return ;
}
void tospread(in p,int w1,int w2){
    t[p].lazy=t[p].lazy+w1;
    t[p].lazy1=t[p].lazy1+w2;

    t[p].sum=t[p].sum+w1;
    t[p].sum1=t[p].sum1+w2;

    return ;
}
//void tospread1(in p,int w){
//    t[p].lazy2=t[p].lazy2+w;
//    t[p].sum2=t[p].sum2+w;
//    return ;
//}
void spread(in p){
    tospread(p<<1,t[p].lazy,t[p].lazy1);
    tospread(p<<1|1,t[p].lazy,t[p].lazy1);
    t[p].lazy=t[p].lazy1=0;
    return ;
}
//void spread1(in p){
//    tospread1(p<<1,t[p].lazy2);
//    tospread1(p<<1|1,t[p].lazy2);
//    t[p].lazy2=0;
//    return ;
//}
void change(in p,in l,in r,int w1,int w2){
    if(l>r)return ;
    if(t[p].l>=l&&t[p].r<=r){
        tospread(p,w1,w2);
        return ;
    }
    if(t[p].lazy||t[p].lazy1)spread(p);
//    if(t[p].lazy2)spread1(p);
    in mid=t[p].l+t[p].r>>1;
    if(l<=mid)change(p<<1,l,r,w1,w2);
    if(r>mid)change(p<<1|1,l,r,w1,w2);
    update(p);
    return ;
}
//void change1(in p,in l,in r,int w){
//    if(l>r)return ;
//    if(t[p].l>=l&&t[p].r<=r){
//        tospread1(p,w);
//        return ;
//    }
//    if(t[p].lazy||t[p].lazy1)spread(p);
//    if(t[p].lazy2)spread1(p);
//    in mid=t[p].l+t[p].r>>1;
//    if(l<=mid)change1(p<<1,l,r,w);
//    if(r>mid)change1(p<<1|1,l,r,w);
//    update(p);
//    return ;
//}
int ask(in p,in l,in r){
//    cout<<t[p].l<<" "<<t[p].r<<"   "<<l<<" "<<r<<endl;
    if(l>r)return 0;
    if(t[p].l>=l&&t[p].r<=r)return t[p].sum;
    int mid=t[p].l+t[p].r>>1,ans=0;
    if(t[p].lazy||t[p].lazy1)spread(p);
//    if(t[p].lazy2)spread1(p);
    if(l<=mid)ans=ask(p<<1,l,r);
    if(r>mid)ans=ans+ask(p<<1|1,l,r);
    if(ans>stan)ans%=mod;
    return ans;
}
int ask1(in p,in l,in r){
    if(l>r)return 0;
    if(t[p].l>=l&&t[p].r<=r)return t[p].sum1;
    in mid=t[p].l+t[p].r>>1,ans=0;
    if(t[p].lazy||t[p].lazy1)spread(p);
//    if(t[p].lazy2)spread1(p);
    if(l<=mid)ans=ask1(p<<1,l,r);
    if(r>mid)ans=ans+ask1(p<<1|1,l,r);
    if(ans>stan)ans%=mod;
    return ans;
}
int ask2(in p,in l,in r){
    if(l>r)return 0;
    if(t[p].l>=l&&t[p].r<=r)return t[p].sum2;
    in mid=t[p].l+t[p].r>>1,ans=0;
    if(t[p].lazy||t[p].lazy1)spread(p);
//    if(t[p].lazy2)spread1(p);
    if(l<=mid)ans=ask2(p<<1,l,r);
    if(r>mid)ans=ans+ask2(p<<1|1,l,r);
    if(ans>stan)ans%=mod;
    return ans;
}
int solve(in u,int w,in op){
    int res=0;
    int sumz=0;
    if(siz[u]>1)sumz=ask3(dfn[u]+siz[u]-1)-ask3(dfn[u]);
//    int sumz=ask2(1,dfn[u]+1,dfn[u]+siz[u]-1);
//    cout<<"hhh "<<u<<" "<<sumz<<endl;
//    cout<<ask(1,dfn[u]+1,dfn[u]+siz[u]-1)<<" "<<ask(1,dfn[u],dfn[u])<<endl;
    //cout<<"hhh"<<endl;
    int suml=ask(1,dfn[fa[u]],dfn[fa[u]])%mod;
//    cout<<" "<<ask1(1,dfn[fa[u]],dfn[fa[u]])<<endl;
    modadd(res,ask1(1,dfn[fa[u]],dfn[fa[u]])%mod*n%mod-suml);
//    cout<<res<<endl;
//    cout<<sumtot<<" "<<suml<<" "<<sumz<<endl;
    modadd(res,sumtot-suml-siz[u]*val[u]%mod-sumz);
//    cout<<res<<endl;
    res=2*res*siz[u]%mod*w%mod;
//    cout<<res<<endl;
    modadd(res,2*w*(n-siz[u])%mod*sumz%mod);
//    cout<<"hhh "<<res<<endl;
//    cout<<res<<endl;
    if(op){
        change(1,dfn[u],dfn[u]+siz[u]-1,w*siz[u]%mod,w);
        change1(dfn[u],w*siz[u]%mod);
//        change1(1,dfn[u],dfn[u],w*siz[u]);
        modadd(sumtot,w*siz[u]%mod);
    }
    return res;
}
int po(int a,int b=mod-2){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
signed main(){
//    freopen("revive3.in","r",stdin);
//    freopen("shuju.in","r",stdin);
//    freopen("my.out","w",stdout);
    n=read();
    n=read(),m=read();
    for(int i=2;i<=n;i++){
        fa[i]=read();
        val[i]=read();
        add(fa[i],i);
    }
    dfs(1);
    dfs1(1);
    build(1,1,n);
    for(int i=1;i<=n;i++)change1(dfn[i],siz[i]*val[i]%mod);
    for(int i=1;i<=n;i++)modadd(sumtot,val[i]*siz[i]%mod);
    for(int i=2;i<=n;i++){
//        cout<<"id: "<<i<<endl;
//        cout<<solve(i,val[i],0)<<" ";
        ans=(ans+solve(i,val[i],0))%mod;
    }
    ans=ans*po(2)%mod;
//    cout<<ans<<endl;
    for(int i=2;i<=n;i++){
        ans=(ans+val[i]*val[i]%mod*siz[i]%mod*(n-siz[i])%mod)%mod;
    }
    cout<<ans<<endl;
    for(int i=1;i<=m;i++){
        x=read();
        w=read();
        ans=(ans-val[x]*val[x]%mod*siz[x]%mod*(n-siz[x])%mod)%mod;
        ans=(ans+mod)%mod;
        ans=(ans+solve(x,w,1))%mod;
        val[x]+=w;
        val[x]%=mod;
        ans=(ans+val[x]*val[x]%mod*siz[x]%mod*(n-siz[x])%mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}