题目链接：http://115.236.49.52:83/contest/1351
A题:
题解：假设n是奇数。n如果是偶数，翻转90度就可以了。
B题：
#include <bits/stdc++.h>
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\n", ans);
return 0;
}
#include <bits/stdc++.h>
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\n", ans);
return 0;
}
D:
我的做法只能过前4个测试点。
京公网安备 11010502036488号