考察:树形dp
错误思路:
换根dp,正向点权值0,逆向点权值1.求每个点到其他点的距离和.
此思路错在会多次计算要旋转的边.
思路:
换根dp,需要两次dfs求当前结点i往下走的逆转数和往上走的逆转数.向下走的计算很容易 f[u][1]+=f[v][1]+road[i].w
向上走如果直接推会有点难推,我们要从虚根结点出发往下推,用父节点更新子结点.(一定要从起点开始往下推啊TAT)
f[v][0] += f[u][0]+f[u][1]-f[v][1]-road[i].w+rw
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int N = 200010; 6 int n,f[N][2],idx,h[N]; 7 struct Road{ 8 int to,ne,w; 9 }road[N<<1]; 10 void add(int a,int b,int c) 11 { 12 road[idx].w = c,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++; 13 } 14 void dfs_up(int u,int fa) 15 { 16 for(int i=h[u];i!=-1;i=road[i].ne) 17 { 18 int v = road[i].to; 19 if(v==fa) continue;//向上走要连的边 20 int rw = road[i].w^1; 21 f[v][0] = f[u][1]-f[v][1]-road[i].w+rw+f[u][0]; 22 dfs_up(v,u); 23 } 24 } 25 void dfs(int u,int fa) 26 { 27 for(int i=h[u];i!=-1;i=road[i].ne) 28 { 29 int v = road[i].to; 30 if(v==fa) continue; 31 dfs(v,u); 32 f[u][1] += f[v][1]+road[i].w; 33 } 34 } 35 int main() 36 { 37 while(scanf("%d",&n)!=EOF) 38 { 39 memset(h,-1,sizeof h); 40 memset(f,0,sizeof f); 41 for(int i=1;i<n;i++) 42 { 43 int a,b; scanf("%d%d",&a,&b); 44 add(a,b,0); add(b,a,1); 45 } 46 dfs(1,-1); 47 dfs_up(1,-1); 48 int ans = 1e9; 49 for(int i=1;i<=n;i++) ans = min(ans,f[i][0]+f[i][1]); 50 printf("%d\n",ans); 51 for(int i=1;i<=n;i++) 52 if(f[i][0]+f[i][1]==ans) printf("%d ",i); 53 printf("\n"); 54 } 55 return 0; 56 }