考察:树形dp
思路:
参考大佬的思路,本蒟蒻还以为是有依赖的背包问题,但是直接开背包数组会MLE.
定义f[i]为以i为根节点的子树中,最大的结点和.f[i] = max(f[i],f[j](j为i的所有直接或间接的子节点)).
这道题是选两个不相干的最大子树和,需要在每个结点处取最值. ans = max(f[v]+f[u],ans)(u为更新当前子节点v前的最大子树和,v是当前子树和)
因为一个结点的两个子树是一定不相交的,所以可以这么写.
但这道题还有几个坑点:
- 开long long
- 最小值不能太小,否则会爆LL
- 不可能的情况不能更新ans,否则会使最小值变小,也不能以>INF/2为impossible的依据,因为真有可能取到INF/2....
- 输出是ll,不是%d...
1 #include <iostream> 2 #include <cstring> 3 #include <set> 4 using namespace std; 5 typedef long long LL; 6 const int N = 200010; 7 const LL INF = -2e14; 8 int w[N],n,h[N],idx; 9 LL f[N],res = INF; 10 struct Road{ 11 int to,ne; 12 }road[N<<1]; 13 void add(int a,int b) 14 { 15 road[idx].to = b,road[idx].ne = h[a],h[a] = idx++; 16 } 17 LL dfs(int u,int fa) 18 { 19 LL sum = w[u]; 20 for(int i=h[u];i!=-1;i=road[i].ne) 21 { 22 int v = road[i].to; 23 if(v==fa) continue; 24 sum+= dfs(v,u);//以u为根的子树和. 25 if(f[v]!=INF&&f[u]!=INF) res = max(res,f[u]+f[v]); 26 f[u] = max(f[u],f[v]); 27 } 28 f[u] = max(sum,f[u]); 29 return sum; 30 } 31 int main() 32 { 33 scanf("%d",&n); 34 for(int i=1;i<=n;i++) scanf("%d",&w[i]); 35 for(int i=1;i<=n;i++) f[i] = INF; 36 memset(h,-1,sizeof h); 37 for(int i=1;i<n;i++) 38 { 39 int a,b; scanf("%d%d",&a,&b); 40 add(a,b); add(b,a); 41 } 42 dfs(1,-1); 43 if(res!=INF) printf("%lld\n",res); 44 else puts("Impossible"); 45 return 0; 46 }