树形dp，在树结构上，求最优值，求方案等dp问题，就可以考虑是树形dp
试了好几遍才a。。
方法很多，来我的
g【i】：一个人走完子树的最短dis
sum【i】：子树的总边距离乘二，就是一个人走完回到根的路程
f【i】【0】：表示两者在同一个子树中的最短距离
f【i】【1】：表示两者在不同子树中的最短距离
感觉状态的表难想，细节难处理。
这里的状态，我感觉，是根据题目的性质，分情况（因为只有可能两人在同一个子树或不同的子树两种情况），分情况来表示状态，在为了这两个状态才来维护一些其他的东西。
转移实际上推一推就出来了
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> using namespace std; const int inf=0x3f3f3f3f; int f[100010][2],g[100010],sum[100010]; int n,s,fa[100010]; int head[100010],tot; struct aa { int to,pre,dis; }edge[100010]; void addedge(int x,int y,int z) { edge[++tot].to=y;edge[tot].dis=z;edge[tot].pre=head[x];head[x]=tot; } void dfs(int u) { int fi=0,se=0; for (int i=head[u];i;i=edge[i].pre) { int v=edge[i].to; if (fa[u]==v) continue; sum[v]=edge[i].dis*2; g[v]=edge[i].dis; fa[v]=u; dfs(v); if (sum[v]-g[v]>fi) se=fi,fi=sum[v]-g[v]; else if (sum[v]-g[v]>se) se=sum[v]-g[v];//注意如果只有1个孩子怎么办 sum[u]+=sum[v]; } int disfa=g[u]; f[u][1]=sum[u]-fi-se;//注意，两个人如果在u这个子树中，那么disfa就是走了两次，我就是在这里错了 g[u]=sum[u]-fi-disfa; f[u][0]=inf; for (int i=head[u];i;i=edge[i].pre) { int v=edge[i].to; if (v==fa[u]) continue; f[u][0]=min(min(f[v][0],f[v][1])+sum[u]-sum[v],f[u][0]); } if (f[u][0]==inf) f[u][0]=sum[u]; } int main() { scanf("%d%d",&n,&s); int x,y,z; for (int i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); addedge(y,x,z); } dfs(s); printf("%d\n",min(f[s][1],f[s][0])); return 0; }
