学軍信友隊趣味ネット招待試合A-B-D思考+樹形DP/直径+数論


タイトルリンク:http://115.236.49.52:83/contest/1351学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论_第1张图片 学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论_第2张图片題解:nが奇数であると仮定する.nが偶数なら90度反転すればいいです.学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论_第3张图片 学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论_第4张图片 学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论_第5张图片 在这里插入图片描述
B:
#include 
using namespace std;
#define LL long long
 
vector<vector<int> > v(50005);
int a[50005];
LL f[50005][1005];
LL ans=0;
void DFS(int u, int fa){
 
    f[u][a[u]]=max(f[u][a[u]], 0ll);
    for(auto x: v[u]){
        if(x!=fa){
            DFS(x, u);
            LL mx1=0, mx2=0;
            for(int i=1; i<=1000; i++){
 
                if(f[x][i]!=-1) f[x][i]+=1;
                mx1=max(mx1, f[u][i]); mx2=max(mx2, f[x][i]);
                if(f[x][i]!=-1){
                    ans=max(ans, (f[x][i]+mx1)*i);
                }
                if(f[u][i]!=-1){
                    ans=max(ans, (f[u][i]+mx2)*i);
                }
                if(f[x][i]!=-1) f[u][i]=max(f[u][i], f[x][i]);
            }
        }
    }
}
 
int main() {
 
    memset(f, -1, sizeof(f));
    int n, x, y; scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    for(int i=1; i<n; i++){
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1, 0);
    printf("%lld
"
, ans); return 0; } #include using namespace std; #define LL long long const int maxn=5e4+10; struct E{ int to, w; E(int a, int b){ to=a; w=b; } }; vector<E> e[maxn]; int k, d, pos1, pos2; int vis[maxn], a[maxn]; void dfs(int u, int fa, int s){ vis[u]=1; if(s>=d){ d=s, k=u; } for(int i=0;i<e[u].size();i++){ int v=e[u][i].to, w=e[u][i].w; if(v!=fa){ dfs(v, u, s+w); } } } LL ans=0; void dfs(int u, int fa, LL x, LL s){ if(a[u]>=a[x]){ ans=max(ans, s*a[u]); } for(auto to: e[u]){ if(to.to!=fa){ dfs(to.to, u, x, s+to.w); } } } int main() { int n, u, v, w; scanf("%d", &n); for(int i=1; i<=n; i++){ scanf("%d", &a[i]); } for(int i=1; i<n; i++){ scanf("%d%d",&u,&v);w=1; e[u].push_back(E(v, w)); e[v].push_back(E(u, w)); } pos1=pos2=k=0; dfs(1, 0, 0); pos1=k; dfs(k, 0, 0); pos2=k; dfs(pos1, 0, pos1, 0); dfs(pos2, 0, pos2, 0); printf("%lld
"
, ans); return 0; }

学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论_第6张图片 学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论_第7张图片 学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论_第8张图片 学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论_第9张图片