9.02

训练赛传送门

Problem I. Minimum Diameter Spanning Tree

这道题需要一定的前置知识，比如这篇博客

当明白图的绝对中心这个概念后，这道题就迎刃而解了。

注意理解上述博客中的折线最低点的求解过程。因为都是斜率为1的折线，所以可以通过简单的推导得到最低点与折线的关系式，进而求解。然后最后找点则根据中心点的位置bfs即可，注意中心点可能在某条线段的端点上，所以这种情况下要特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int>pli;
typedef double db;
const int maxn=500+5;
const ll mod=998244353;
const double eps=1e-10;
int n,m,fu,fv,fflag,ftot;
ll ans=1e18,flen;
ll dis[505][505];
struct Edge{
	int v;
	ll c;
};
vector<Edge>e[maxn];
pli a[505][505];
ll ndis[maxn];
int vis[maxn],fa[maxn];
void dij(){
	ndis[fu]=flen;
	ndis[fv]=ftot-flen;
	if(fflag){
		if(flen==ftot)fa[fu]=fv;
		else fa[fv]=fu;
	}
	vis[fu]=1,vis[fv]=1;
	priority_queue<pli,vector<pli>,greater<pli>>q;
	q.push({ndis[fu],fu});q.push({ndis[fv],fv});
	while(!q.empty()){
		pli p=q.top();q.pop();
		vis[p.second]=0;
		for(auto cur:e[p.second]){
			if(cur.c*2+ndis[p.second]<ndis[cur.v]){
				ndis[cur.v]=cur.c*2+ndis[p.second];
				if(!vis[cur.v])q.push({ndis[cur.v],cur.v});
				vis[cur.v]=1;
				fa[cur.v]=p.second;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!fa[i])continue;
		printf("%d %d\n",fa[i],i);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++)dis[i][j]=dis[j][i]=1e18;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		ll l;
		scanf("%d%d%lld",&x,&y,&l);
		e[x].push_back({y,l});
		e[y].push_back({x,l});
		dis[x][y]=dis[y][x]=l;
	}
	
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)a[i][j]={dis[i][j],j};
		sort(a[i]+1,a[i]+n+1);
	}
	for(int u=1;u<=n;u++){
		for(auto cur:e[u]){
			ll c=cur.c,temp=ans,len=0;
			int v=cur.v,flag=0;
			if(ans>a[u][n].first*2){
				ans=a[u][n].first*2;
				len=0;
				flag=1;
			}
			if(ans>a[v][n].first*2){
				ans=a[v][n].first*2;
				len=c*2;
				flag=1;
			}
			int pre=n;
			for(int i=n-1;i>=1;i--){
				if(dis[v][a[u][pre].second]<dis[v][a[u][i].second]){
					if(ans>dis[u][a[u][i].second]+dis[v][a[u][pre].second]+c){
						ans=dis[u][a[u][i].second]+dis[v][a[u][pre].second]+c;
						len=ans-dis[u][a[u][i].second]*2;
					}
					pre=i;
				}
			}
			if(ans<temp)fu=u,fv=v,flen=len,fflag=flag,ftot=c*2;
		}
	}
	printf("%lld\n",ans);
	if(!fflag)printf("%d %d\n",fu,fv);
	memset(ndis,0x3f,sizeof(ndis));
	dij();
	return 0;
}

Problem K. Wind of Change

首先进行点分治，这样一来，对于每个点而言，最多就只有 lognlogn 个祖先。

然后存下来每个点到它的祖先的距离，由于有两张图，所以当固定某个点 ii 时，每张图都有lognlogn个祖先，总共有log2nlog^2n种组合方式。由于我们要构造disgraph0(i,j)+disgraph1(i,j)dis_{graph0}(i,j)+dis_{graph1}(i,j)最小，我们可以直接记录在每个祖先节点到其子树内其它点的最小距离和第二小距离，这样就可以直接与第一小距离或者第二小距离加起来取最小值即是答案。

我们这样得到的答案肯定会包含最优的合法解，同时不合法解的值肯定比最优的大（如果选定的两个祖先不是ii和jj的lca，那么算出来的值肯定比真实的距离大），所以正确性得到证明

注意，由于这个题不能用map，甚至unordered_map也会TLE。所以需要在分治第二棵树的过程中更新答案。由于空状态时用00表示，而有的sumsum可能为00，所以这里我把所有的sumsum都+1+1了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
typedef long long ll;
const ll inf=1e18;
struct Edge{
	int v;
	ll w;
};
vector<Edge>e[2][maxn];
int n,rt,tot;
int vis[maxn];
vector<ll>a[2][maxn];
int fa[2][maxn],sz[maxn],mx[maxn];
ll dis[maxn];
ll ans[maxn];
ll fst[maxn],scd[maxn];
void get_rt(int u,int p,int sgn){
	sz[u]=1;mx[u]=0;
	for(auto cur:e[sgn][u]){
		int v=cur.v;
		if(v==p||vis[v])continue;
		get_rt(v,u,sgn);
		sz[u]+=sz[v];
		mx[u]=max(sz[v],mx[u]);
	}
	mx[u]=max(mx[u],tot-sz[u]);
	if(mx[rt]>mx[u])rt=u;
}
void cal(int u,int p,int sgn){
	a[sgn][u].push_back(dis[u]);
	for(auto cur:e[sgn][u]){
		int v=cur.v;
		ll w=cur.w;
		if(v==p||vis[v])continue;
		dis[v]=dis[u]+w;
		cal(v,u,sgn);
	}
}
void solve(int u,int up,int sgn){
	vis[u]=1;fa[sgn][u]=up;
	dis[u]=0;cal(u,0,sgn);
	for(auto cur:e[sgn][u]){
		int v=cur.v;
		if(vis[v])continue;
		tot=sz[v];
		rt=0;
		get_rt(v,0,sgn);
		solve(rt,u,sgn);
	}
}
void check(int u,int p,int sgn){
	int cnt=a[0][u].size();
	for(int i=u;i;i=fa[0][i]){
		cnt--;
		ll sum=a[0][u][cnt]+dis[u]+1;
		if(!fst[i]){
			fst[i]=sum;
			scd[i]=inf;
		}
		else {
			if(sum<fst[i]){
				scd[i]=fst[i];
				fst[i]=sum;
			}
			else if(sum<scd[i]){
				scd[i]=sum;
			}
		}
	}
	for(auto cur:e[sgn][u]){
		int v=cur.v;
		ll w=cur.w;
		if(v==p||vis[v])continue;
		dis[v]=dis[u]+w;
		check(v,u,sgn);
	}
}
void modify(int u,int p,int sgn){
	int cnt=a[0][u].size();
	for(int i=u;i;i=fa[0][i]){
		cnt--;
		ll sum=a[0][u][cnt]+dis[u]+1;
		if(fst[i]==sum)ans[u]=min(ans[u],sum+scd[i]);
		else ans[u]=min(ans[u],sum+fst[i]);
	}
	for(auto cur:e[sgn][u]){
		int v=cur.v;
		if(v==p||vis[v])continue;
		modify(v,u,sgn);
	}
}
void clear(int u,int p,int sgn){
	for(int i=u;i;i=fa[0][i]){
		fst[i]=scd[i]=0;
	}	
	for(auto cur:e[sgn][u]){
		int v=cur.v;
		if(v==p||vis[v])continue;
		clear(v,u,sgn);
	}
}
void find(int u,int up,int sgn){
	vis[u]=1;fa[sgn][u]=up;
	dis[u]=0;
	check(u,0,sgn);
	modify(u,0,sgn);
	clear(u,0,sgn);
	for(auto cur:e[sgn][u]){
		int v=cur.v;
		if(vis[v])continue;
		tot=sz[v];
		rt=0;
		get_rt(v,0,sgn);
		find(rt,u,sgn);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;ll w;
		scanf("%d%d%lld",&u,&v,&w);
		e[0][u].push_back({v,w});
		e[0][v].push_back({u,w});
	}
	for(int i=1;i<n;i++){
		int u,v;ll w;
		scanf("%d%d%lld",&u,&v,&w);
		e[1][u].push_back({v,w});
		e[1][v].push_back({u,w});
	}	
	tot=n;
	mx[0]=n+1;
	get_rt(1,0,0);
	solve(rt,0,0);
	memset(vis,0,sizeof(vis));
	memset(ans,0x3f,sizeof(ans));
	tot=n;
	rt=0;
	get_rt(1,0,1);
	find(rt,0,1);		
	for(int i=1;i<=n;i++)printf("%lld\n",ans[i]-2);
	return 0;
}