樹上子鍊
題意:
給定一棵樹 T ,樹 T 上每個點都有一個權值。
定義一顆樹的子鍊的大小為:這個子鍊上所有結點的權值和 。
請在樹 T 中找出一條最大的子鍊并輸出。
題解:
求樹的直徑,題目中存在負權值,樹形dp求樹的直徑可以處理負邊權直徑的模闆:
void DP(int u,int pa)
{
dp[u]=0;
for(int i=head[u];i;i=E[i].nxt)
{
int v=E[i].v;
if(v==pa) continue;
DP(v,u);
mxlen=max(mxlen,dp[u]+dp[v]+E[i].dis);//這裡直接用一個全部變量更新也可以
dp[u]=max(dp[u],dp[v]+E[i].dis);
}
}
另兩個dfs也可以求直徑,但是負邊權不行
代碼:
#include<bits/stdc++.h>
#define debug(a,b) printf("%s = %d\n",a,b);
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
const int maxn=2e5+9;
vector< int>vec[maxn];
ll a[maxn];
ll dp[maxn];
ll ans=-0x3f3f3f;
void get_dp(int u,int fa){
dp[u]=a[u];
ans=max(ans,a[u]);
for(int i=0;i<vec[u].size();i++){
int v=vec[u][i];
if(v==fa)continue;
get_dp(v,u);
ans=max(ans,dp[u]+dp[v]);
dp[u]=max(dp[u],dp[v]+a[u]);
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
vec[u].push_back(v);
vec[v].push_back(u);
}
get_dp(1,-1);
cout<<ans;
}
這個代碼中max1和max2分别表示最大值和次大值
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
vector<int> G[100005];
int n;
ll ans=-1e16;
ll dp[100005];//以i為根節點,到葉子節點的最大路徑
void dfs(int now,int fa)
{
ll max1=a[now],max2=a[now];//max1 到葉子節點的最大路徑 max2次大路徑
for(auto t:G[now])
{
if(t==fa) continue;
dfs(t,now);
if(dp[t]+a[now]>max1)//維護max1
{
max2=max1;
max1=dp[t]+a[now];
}
else if(dp[t]+a[now]>max2)//維護max2
{
max2=dp[t]+a[now];
}
}
dp[now]=max1;
ans=max(ans,max1+max2-a[now]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
printf("%lld\n",ans);
}