【猜结论+Tree】ICPC 昆明 F Find the Maximum

男娘i 2024-03-16 10:08 43阅读 0赞

**vp的时候结论没猜出来....**

**其实想的时候有点接近了，但是就是没想到路径长度为2或3的情况**

**其实打个暴力，然后手动搞几组例子输进去，归纳一下就能猜出结论了**

**但是因为我们懒得搞样例，导致没猜出来....**

题意：

给定一棵树，问你对于所有的简单路径，下面这个式子最大值是多少

![170ba300917e4934b6a9eabdbeaa031a.png][]

思路：

考虑一条长度>=4的路径，将其对半分，因为长度/2，权值和有一段<原来的1/2，有一段>原来的1/2，因此>原来的1/2的那段的均值就乘了个大于等于1的值，一定不差于原来一整段，那么就可以一直分下去，直到分到长度为2或者3的链

那么我们可以枚举所有长度为2或者3的链，然后统计最大值即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    vector<int> G[mxn];
    
    int N,u,v;
    int b[mxn];
    
    bool cmp(int x,int y){
        return b[x]<b[y];
    }
    void solve(){
        cin>>N;
        for(int i=0;i<N;i++) cin>>b[i];
        double ans=-1e18*1.0;
        for(int i=1;i<=N-1;i++){
            cin>>u>>v;
            u--,v--;
            G[u].push_back(v);
            G[v].push_back(u);
            ans=max(ans,1.0*(b[u]+b[v])*(b[u]+b[v])/16.0);
        }
        for(int i=0;i<N;i++){
            sort(G[i].begin(),G[i].end(),cmp);
            if(G[i].size()<2) continue;
            int xx=b[i],yy=b[G[i][0]],zz=b[G[i][1]];
            ans=max(ans,(xx+yy+zz)*(xx+yy+zz)*1.0/36.0);
            int m=G[i].size();
            xx=b[i],yy=b[G[i][m-2]],zz=b[G[i][m-1]];
            ans=max(ans,(xx+yy+zz)*(xx+yy+zz)*1.0/36.0);
        }
        cout<<fixed<<setprecision(6)<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[170ba300917e4934b6a9eabdbeaa031a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/14f4db48b31e40558f5a401c151b9824.png