NOIp 2014 联合权值 By cellur925

这题自己（真正）思考了很久（欣慰）。

（轻而易举）地发现这是一棵树后，打算从Dfs序中下功夫，推敲了很久规律，没看出来（太弱了）。

开始手动枚举距离为2的情况，模模糊糊有了一些概念，但没有总结。（敲黑板：题目中发现规律与重要性质注意总结！）

其实，距离为2的情况只有两种：祖父/兄弟。

一个小时后放弃治疗。开始想暴力，很好想，我们对于每个点，枚举他的出边，再在每个出边中的出边中进行枚举，储存距离为2 的点。期望得分60pts.

大力交了一下：40pts,AC*6,WA*2,MLE*4.

MLE还有情可缘，vector开动态数组可能炸了，WA的那两个喵喵喵？

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 typedef long long ll;

 int n,tot;

 ll sum,ans,p=;

 int head[];

 ll val[];

 bool vis[];

 struct node{

     int to,next;

 }edge[];

 vector<int>law[];

 void add(int x,int y)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 void dfs(int u)

 {

     for(int i=head[u];i;i=edge[i].next)

     {

         int v=edge[i].to;

         for(int j=head[v];j;j=edge[j].next)

         {

             int g=edge[j].to;

             if(g==u) continue;

             law[u].push_back(g);

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n-;i++)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         add(x,y);

         add(y,x);

     }

     for(int i=;i<=n;i++) scanf("%d",&val[i]);

 //    dfs_pre(1);

 //    memset(vis,0,sizeof(vis));

 //    dfs(1,0);

     for(int i=;i<=n;i++)

         dfs(i);

     for(int i=;i<=n;i++)

     {

         for(int j=;j<law[i].size();j++)

         {

             int u=i,v=law[i][j];

             ll tmp=val[u]%p*val[v]%p;

             (sum+=tmp)%=p;

             (ans=max(ans,tmp))%=p;

         }

     }

     printf("%lld %lld",ans,sum);

     return ;

 }

后来经过冷静分析看题解发现并不需要存儿子，当时每次更新一下就行了。而且最大值并不需要取膜。

再交一下60pts。TLE4个点，正常。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 typedef long long ll;

 int n,tot;

 ll sum,ans,p=;

 int head[];

 ll val[];

 struct node{

     int to,next;

 }edge[];

 void add(int x,int y)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 void dfs(int u)

 {

     for(int i=head[u];i;i=edge[i].next)

     {

         int v=edge[i].to;

         for(int j=head[v];j;j=edge[j].next)

         {

             int g=edge[j].to;

             if(g==u) continue;

             ans=max(ans,val[u]*val[g]);

             (sum+=val[u]*val[g])%=p;

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n-;i++)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         add(x,y);

         add(y,x);

     }

     for(int i=;i<=n;i++) scanf("%d",&val[i]);

 //    dfs_pre(1);

 //    memset(vis,0,sizeof(vis));

 //    dfs(1,0);

     for(int i=;i<=n;i++)

         dfs(i);

     printf("%lld %lld",ans,sum);

     return ;

 }

正解：我们只需要枚举每个点与他相连的每一条边即可，统计出与每个点相邻的最大点值与次大点值，全局最值用（最大点值*次大点值）更新，全局和用“乘法分配律“”维护。

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 int n,tot;

 ll p=,sum,ans;

 int head[],val[];

 struct node{

     int to,next;

 }edge[];

 void add(int x,int y)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 ll llmax(ll a,ll b)

 {

     if(a>=b) return a;

     else return b;

 }

 void update(int x)

 {

     int maxx=,maxs=;

     ll cnt=;

     for(int i=head[x];i;i=edge[i].next)

     {

         int y=edge[i].to;

         if(val[y]>maxx) maxs=maxx,maxx=val[y];

         else if(val[y]>maxs) maxs=val[y];

         (sum+=cnt*val[y])%=p;

         (cnt+=val[y])%=p;

     }

     ans=llmax(ans,maxs*maxx);

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n-;i++)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         add(x,y);add(y,x);

     }

     for(int i=;i<=n;i++) scanf("%d",&val[i]);

     for(int i=;i<=n;i++) update(i);

     printf("%lld %lld",ans,*sum%p);

     return ;

 }

巴特西

NOIp 2014 联合权值 By cellur925

最新文章

热门文章