这道题是说，给出一棵树，每个节点有一个权值，要求去掉一条边所能获得的两棵树的最小的权值差，其实不能说是dp因为除了最后一步涉及到了取最小之外，其他的地方都是在枚举而已，没有什么状态转移之类的东西存在，只能说是一道简单的树形的搜索
View Code 1 #include2 #include 3 #include 4 #define N 100005 5 #define M 1000005 6 using namespace std; 7 int head[N]; 8 struct edge 9 {10 int v;11 int next;12 };13 edge e[M];14 int t;15 long long v[N];16 long long dp[N];17 bool used[N];18 void init()19 {20 memset(head,-1,sizeof(head));21 memset(used,0,sizeof(used));22 memset(dp,0,sizeof(dp));23 t=0;24 }25 void add(int x,int y)26 {27 e[t].v=x;28 e[t].next=head[y];29 head[y]=t++;30 e[t].v=y;31 e[t].next=head[x];32 head[x]=t++;33 }34 void dfs(int u)35 {36 used[u]=true;37 dp[u]=v[u];38 int i;39 for(i=head[u];i>=0;i=e[i].next)40 {41 if(!used[e[i].v])42 {43 dfs(e[i].v);44 dp[u]+=dp[e[i].v];45 }46 }47 }48 long long abs(long long x)49 {50 return x>=0?x:-x;51 }52 long long min(long long a,long long b)53 {54 return a