[JSOI2013]旅行时的困惑

链接：https://www.luogu.com.cn/problem/P5258 题目描述：给定一颗有向树，求至少多少条有向路径可以覆盖整颗树(有向路径可以相交) 题解：路径的覆盖，我们容易想到赛道修建那样的半链树型$dp$。但这题边有两种方向，于是我们令$f_{x}$表示以$x$为端点向下半链，$g_{x}$表示以$x$为端点向上半链。 我们可以发现，每一次至多消除两条半链：一条向上，一条向下，至少消除一条半链。所以对于每一个节点$x$，我们直接消除上半链与下半链的匹配肯定不会使答案更差。 这样消除完后还剩下一些相同方向的半链，由于路径可以相交，我们可以把它们全都上传到父亲节点。因为在$x$节点消每一次只能消一条半链，说不定在父亲节点还能消除两条半链，所以我们可以将所有的半链上传到父亲节点。 注意:根节点不能上传半链。 ``` #include #include using namespace std; struct node { int v,nxt,data; }; node edge[1000001]; int u,n,ans,len,head[1000001],fa[1000001],f[1000001],g[1000001]; bool used[1000001]; int visfa[1000001]; void add(int x,int y,int z) { edge[++len].v=y; edge[len].data=z; edge[len].nxt=head[x]; head[x]=len; return; } void dfs(int x) { used[x]=1; for (int i=head[x];i>0;i=edge[i].nxt) if (!used[edge[i].v]) { fa[edge[i].v]=x; visfa[edge[i].v]=edge[i].data; dfs(edge[i].v); } u=min(f[x],g[x]); f[x]-=u; g[x]-=u; ans+=u; if (x==1) { ans+=f[x]+g[x]; return; } if (visfa[x]==0) { f[fa[x]]+=max(f[x],1); ans+=g[x]; } else { g[fa[x]]+=max(g[x],1); ans+=f[x]; } return; } int main() { int x,y; cin>>n; for (int i=1;i<=n-1;++i) { cin>>x>>y; x++; y++; add(x,y,1); add(y,x,0); } dfs(1); cout<