8
1
1
2
1
1
1
1
3
1 5
2 1
3 1
8 3
6 4
7 4
4 5
0 0
by 混沌 @ 2017-10-21 15:21:36
自己出了一组数据 都可以证明是错的 结果在洛谷 codevs上都A了........
by 混沌 @ 2017-10-21 15:22:46
这我记得是一道数据很水的树形dp啊
我变量打成常数都A了绝大部分点=。=
by moye到碗里来 @ 2017-10-21 16:56:54
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int a[maxn],fa[maxn],n,root,mxdep;
vector<int>dep[maxn],son[maxn];
void dfs(int u,int d,int f)
{
mxdep=max(mxdep,d);
dep[d].push_back(u);
for(int i=0;i<son[u].size();i++)
dfs(son[u][i],d+1,u);
return ;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1,tmp1,tmp2;i<n;i++)
{
scanf("%d%d",&tmp1,&tmp2);
fa[tmp1]=tmp2;
son[tmp2].push_back(tmp1);
}
for(int i=1;i<=n;i++)
if(!fa[i]) root=i;
dfs(root,1,-1);
int ans[2]={0,0};
for(int i=1;i<=mxdep;i++)
for(int j=0;j<dep[i].size();j++)
if(a[dep[i][j]]>0)
ans[i%2]+=a[dep[i][j]];
printf("%d",max(ans[0],ans[1]));
}
```
甚至不需要dp，直接二分图
水的过分了233
by steven张 @ 2018-01-13 20:16:58
#include<cstdio>
const int N=7777;
int son[N][N/77],ans,n,x,y,f[N][2];
inline int max(int x,int y){
return x>y?x:y;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&f[i][1]);
while(1){
scanf("%d%d",&x,&y);
if(x==0&&y==0)
break;
son[y][++son[y][0]]=x;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=son[i][0];j++)
f[i][0]+=max(f[son[i][j]][0],f[son[i][j]][1]),f[i][1]+=f[son[i][j]][0];
for(int i=1;i<=n;i++)
for(int j=0;j<=1;j++)
ans=max(ans,f[i][j]);
printf("%d\n",ans);
return 0;
}
这样居然只有80
by 以墨 @ 2018-04-03 22:31:53