[JSOI2014]支线剧情2

链接：https://vjudge.net/problem/HYSBZ-5031 题目描述：给定一个树形图，规定一号点为根节点。到达一个点时可以进行下列操作： $1$.沿着一条有向边走到下一个节点。 $2$.回到$1$号节点。 $3$.设定当前节点为存档节点。 $4$.回到存档节点。 求遍历完所有点走过的边权和的最小值。 题解：可以发现，每一个点，假如它的祖先中没有被存档的，那么将它存档不会使答案更差。所以对于当前子树，我们要尽量的让他存档。 令$dp_{x}$表示$x$存档时遍历完$x$的子树的最小代价。 则有两种情况： $1$.选择$x$存档并且$x$的子树中除了$x$都不存档。 $2$.选择一个子节点$v$，在遍历完$x$的其他子节点的子树后，将存档节点流放至$v$。 $1$操作很好做，答案就是$f_{x}$(在下面的表述中，$f$表示$x$所有叶节点到$x$的距离和，$sz_{x}$表示$x$的叶结点的个数)，可以直接$dp$。 $2$操作也很好做，假如你选了子节点$v$，则对答案的贡献是$d_{v}+dp_{v}-(f_{v}+sz_{v}+edge)$，选贡献小于$0$的选即可。当然，你选的第一个无需$d_{v}$的代价，由于你选的第一个一定是贡献尽量小的，所以判一下就行了。 ``` #include #include #include using namespace std; struct node { int data,v,nxt; }; node edge[1000001]; int head[1000001],len; bool used[1000001]; long long n,length,fa[1000001],top[1000001],d[1000001],D[1000001],sz[1000001],dp[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; if (head[x]==0) sz[x]=1; for (int i=head[x];i>0;i=edge[i].nxt) if (!used[edge[i].v]) { d[edge[i].v]=d[x]+edge[i].data; dfs(edge[i].v); fa[edge[i].v]=x; D[x]+=(D[edge[i].v]+edge[i].data*sz[edge[i].v]); dp[x]=D[x]; sz[x]+=sz[edge[i].v]; } length=0; for (int i=head[x];i>0;i=edge[i].nxt) if (fa[edge[i].v]==x) top[++length]=dp[edge[i].v]+edge[i].data-(D[edge[i].v]+edge[i].data*sz[edge[i].v]); sort(top+1,top+length+1); for (int i=1;i<=length;++i) dp[x]+=min(top[i]+d[x]*(i!=1),0ll); return; } int main() { long long x,y,z; cin>>n; for (int i=1;i<=n;++i) { cin>>x; while (x--) { cin>>y>>z; add(i,y,z); } } dfs(1); cout<