NOIP模拟测试25

这次考试后面心态爆炸了。。。发现刚了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）,常数较大，代码实现很简单。

 #include<bits/stdc++.h>

 #define mod 1000000007

 #define ll long long

 using namespace std;

 inline ll read(){

     int x=;

     char ch=getchar();

     while(ch<''||ch>'')ch=getchar();

     while(ch>=''&&ch<='')x=(x<<)+(x<<)+ch-,ch=getchar();

     return x;

 }

 int n,f[],fi[],to[],ne[],tot,sb,q;

 ll siz[],al[],fang[],ans,ni,w[];

 inline void add(int x,int y){

     ne[++tot]=fi[x];

     fi[x]=tot;

     to[tot]=y;

 }

 void dfs(int x){

     siz[x]=;al[x]=,fang[x]=;

     for(int i=fi[x];i;i=ne[i]){

         int y=to[i];

         dfs(y);

         al[x]=(al[x]+al[y]+(siz[y]*w[y]))%mod;

         fang[x]=(fang[x]+fang[y]+al[y]*w[y]*+w[y]*w[y]%mod*siz[y])%mod;

         siz[x]+=siz[y];

     }

 }

 void dfs2(int x){

     ans=(ans+fang[x])%mod;

     for(int i=fi[x];i;i=ne[i]){

         int y=to[i];

         ll  fx=(fang[x]-fang[y]-al[y]*w[y]*-w[y]*w[y]%mod*siz[y])%mod,

             ax=(al[x]-al[y]-(siz[y]*w[y]))%mod;

         fang[y]=(fang[y]+fx+ax*w[y]*+w[y]*w[y]%mod*(n-siz[y]))%mod;

         al[y]=(al[y]+ax+(n-siz[y])*w[y])%mod;

         dfs2(y);

     }

 }

 int main(){

     sb=read(),n=read(),q=read();

     ni=;

     for(int i=;i<=n;i++)f[i]=read(),w[i]=read(),add(f[i],i);

     dfs();

     dfs2();

     printf("%lld\n",(ans+mod)%mod*ni%mod);

     while(q--){

         int u=read();

         ll ad=read();

         w[u]=(w[u]+ad)%mod;

         dfs();

         ans=;

         dfs2();

         printf("%lld\n",(ans+mod)%mod*ni%mod);

     }

     return ;

 }

正解不会，咕了

巴特西

NOIP模拟测试25

最新文章

热门文章