Codeforces 682C Alyona and the Tree（树形DP）

题目大概说给一棵点有权、边也有权的树。一个结点v不高兴当且仅当存在一个其子树上的结点u，使得v到u路径上的边权和大于u的权值。现在要不断地删除叶子结点使得所有结点都高兴，问最少删几个叶子结点。

一开始题目看错了，以为说的是v到u路径上的边权和小于v的权值，然后想出了个解法：从根开始DFS，找高兴的结点，递归过程中在set插入各个祖先结权值，递归返回时从set中删除，而如果set里面最小的元素小于当前结点的路径和那么这个结点就不能要直接return，另外还用到一个简单的数学原理——两个数同时加上相同的数其大小关系不变。。时间复杂度O(nlogn)。

然后写好后才发现读错题。而事实上这题反而更容易。。同样也是从根开始DFS，遇到不高兴的就不往下DFS了，而判断是否高兴就用到个简单的DP了：

dp[u]表示祖先到u结点中的最大边权和
由于边权可以为负，所以转移就是dp[v]=max(dp[u]+weight(u,v),weight(u,v))
而u结点不高兴，当且仅当d[u]>weight(u)

另外可以不用long long，这个是没问题的。。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define MAXN 111111
 6 struct Edge{
 7     int v,w,next;
 8 }edge[MAXN<<1];
 9 int NE,head[MAXN];
10 void addEdge(int u,int v,int w){
11     edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
12     head[u]=NE++;
13 }
14 
15 int val[MAXN],ans;
16 int d[MAXN];
17 void dfs(int u){
18     if(u!=1 && d[u]>val[u]){
19         return;
20     }
21     ++ans;
22     for(int i=head[u]; i!=-1; i=edge[i].next){
23         int v=edge[i].v;
24         d[v]=max(d[u]+edge[i].w,edge[i].w);
25         dfs(v);
26     }
27 }
28 int main(){
29     int n;
30     scanf("%d",&n);
31     for(int i=1; i<=n; ++i){
32         scanf("%d",val+i);
33     }
34     NE=0;
35     memset(head,-1,sizeof(head));
36     int a,b;
37     for(int i=2; i<=n; ++i){
38         scanf("%d%d",&a,&b);
39         addEdge(a,i,b);
40     }
41     dfs(1);
42     printf("%d",n-ans);
43     return 0;
44 }