直径类似的树形dp
递归是核心 都是采用递归找到最优解之后再上来进行操作
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define int long long
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define Yes cout<<"Yes"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;
int w[N],ans;
vector<PII> g[N];
//树形dp 都是从根节点的最优不断向上推理出来的
int dfs(int u,int fa)
{
int d1=0,d2=0;
for(auto &[j,v]:g[u])
{
if(j==fa) continue;
int d=dfs(j,u);// dfs找到最优方案之后开始进行操作
if(d<v) continue;
d-=v;
if(d>=d1) d2=d1,d1=d;
else if(d>d2) d2=d;
}
ans=max(ans,d1+d2+w[u]);// 典型的分类操作
return d1+w[u];
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++)
{
int a,b,c; cin>>a>>b>>c;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
ans=max(ans,dfs(1,-1));
cout<<ans<<endl;
return ;
}
signed main ()
{
ios// 不能有printf puts scanf
solve();
}
典型的题目
//确定状态选不选是核心以及影响是什么
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int f[N][2],w[N];
bool st[N];
vector<int> g[N];
void dfs(int u)
{
f[u][1]=w[u];// 选了自己
for(auto &v:g[u])
{
dfs(v);//由下到上来不断dp找到最优解就是树形dp
f[u][0]+=max(f[v][0],f[v][1]);// 表示选不选的最优解
f[u][1]+=f[v][0];
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++)
{
int a,b; cin>>a>>b;
g[b].push_back(a);
st[a]=true;
}
int root=1;
while(st[root]) root++;// 这样子来找到根节点
dfs(root);
cout<<max(f[root][1],f[root][0])<<endl;
return 0;
}
数据十分水的一道可以联系简单树形dp
//实际上会超时
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
set<int> res[N];
vector<int> g[N];
int n,m;
int w[N],ans[N];// 表示每个位置的颜色,一节每个位置的最后答案是多少
void dfs(int u,int fa)
{
for(auto &v:g[u])
{
if(v==fa) continue;
dfs(v,u);//表示递归到最后来处理
for(auto &t:res[v]) res[u].insert(t);
}
res[u].insert(w[u]);
ans[u]=res[u].size();
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];// 读入颜色
for(int i=1;i<n;i++)
{
int a,b; cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1,-1);// 从根节点开始便利
while(m--)
{
int x; cin>>x;
cout<<ans[x]<<endl;
}
return 0;
}