题解：P4268 [USACO18FEB] Directory Traversal G

容易看出，所有的目录形成了一棵有根树。

首先假设从

1

号点出发，算出此时长度。

定义

siz_i

为以

i

为根的子树中文件的数量，

tot

为所有文件的数量。

假设我们已经知道了从节点

u

出发时的答案

cnt

，那么将出发点变为其子节点

v

，节点

v

下包含的所有文件都长度都会减少

|name_v|+1

，而不在

v

节点下的所有文件访问距离都会增加

3

（需要多访问一次父目录）。

因此，从

u

到

v

，

v

节点的答案即是：

cnt-siz_v\times(|name_v|+1)+3\times(tot-siz_v)

。

从

1

号点出发，不断访问子节点，比较每个子节点的大小即可。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	string name;
	vector<int>son;
	int soncnt;
}a[100005];
int siz[100005];
int fcnt;
int cnt=0,ans=LLONG_MAX;
void dfs(int now,int fa,int dis){
	if(a[now].soncnt==0){
		siz[now]=1;
		cnt+=dis-1;
		return;
	}
	for(int i=0;i<a[now].soncnt;i++){
		int v=a[now].son[i];
		if(v==fa)continue;
		dfs(v,now,dis+1+a[v].name.length());
		siz[now]+=siz[v];
	}
}
void dfs2(int now,int fa,int discnt){
	ans=min(ans,discnt);
	for(int i=0;i<a[now].soncnt;i++){
		int v=a[now].son[i];
		if(v==fa)continue;
//		if(a[v].soncnt==0)continue;
		dfs2(v,now,discnt-(siz[v]*(a[v].name.length()+1-(a[v].soncnt==0)))+(fcnt-siz[v])*3);
	}
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].name>>a[i].soncnt;
		for(int j=1;j<=a[i].soncnt;j++){
			int x;
			cin>>x;
			a[i].son.push_back(x);
		}
		if(a[i].soncnt==0)fcnt++;
	}
	dfs(1,0,0);
	dfs2(1,0,cnt);
	cout<<ans;
	return 0;
}
/*
2
folder1 1 2
file1 0

1
file1 0
*/

题解：P4268 [USACO18FEB] Directory Traversal G

文章操作

相关推荐

评论

题解：P4268 [USACO18FEB] Directory Traversal G