首页 > 代码库 > 【前缀和】【前缀MAX】洛谷 P1351 NOIP2014提高组 day1 T2 联合权值
【前缀和】【前缀MAX】洛谷 P1351 NOIP2014提高组 day1 T2 联合权值
不难发现，树中与某个点距离为2的点只可能是它的父亲的父亲、儿子的儿子 或者 兄弟，分类讨论一下即可。
只有对于兄弟我们不能暴力搞，维护一下每个节点的所有儿子的前缀和、前缀MAX就行了。
1 #include<cstdio> 2 #include<algorithm> 3 #include<vector> 4 using namespace std; 5 #define N 200001 6 #define MOD 10007 7 int n; 8 vector<int>G[N],son[N]; 9 typedef long long ll;10 typedef vector<int>::iterator ITER;11 int x,y,fa[N],dep[N],maxv,sumv,w[N];12 void dfs(int U)13 {14 for(ITER it=G[U].begin();it!=G[U].end();it++)15 if((*it)!=fa[U])16 {17 fa[*it]=U;18 dep[*it]=fa[U]+1;19 son[U].push_back(*it);20 dfs(*it);21 }22 }23 void dfs2(int U)24 {25 if(dep[U]>=2) sumv=(sumv+w[U]*w[fa[fa[U]]]%MOD)%MOD;26 ll All=0,t=0;27 for(ITER it=son[U].begin();it!=son[U].end();it++) All+=(ll)w[*it];28 for(ITER it=son[U].begin();it!=son[U].end();it++)29 {30 t+=(ll)w[*it];31 sumv=(sumv+w[*it]*(int)(All-t)%MOD)%MOD;32 dfs2(*it);33 }34 }35 void dfs3(int U)36 {37 if(dep[U]>=2) maxv=max(maxv,w[U]*w[fa[fa[U]]]);38 int t=0;39 for(int i=0;i<son[U].size();i++)40 {41 if(i)42 {43 t=max(t,w[son[U][i-1]]);44 maxv=max(maxv,w[son[U][i]]*t);45 }46 dfs3(son[U][i]);47 }48 }49 int main()50 {51 scanf("%d",&n);52 for(int i=1;i<n;i++)53 {54 scanf("%d%d",&x,&y);55 G[x].push_back(y);56 G[y].push_back(x);57 }58 for(int i=1;i<=n;i++) scanf("%d",&w[i]);59 dfs(1); dfs2(1); dfs3(1);60 printf("%d %d\n",maxv,(sumv<<1)%MOD);61 return 0;62 }
【前缀和】【前缀MAX】洛谷 P1351 NOIP2014提高组 day1 T2 联合权值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。