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),常数较大,代码实现很简单。

  

NOIP模拟测试25
 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

正解不会,咕了

上一篇:Project Euler 69: Totient maximum


下一篇:LeetCode 69. Sqrt(x)