【牛客OI周赛15-提高组】题解[补题A]
牛客OI周赛15-提高组
https://ac.nowcoder.com/acm/contest/4912
A 环球旅行
给出一棵带边权的树。删除一条边，使分成的两棵树中较大的直径尽量小。求该直径。
我自己的思路：计算直径上的每条边删除后左子树的直径l和右子树的直径r；答案就是min(所有边的max(l,r))
超时，只能得50分
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e6+5;
int n,tot,rt,dis[N],fa[N],h[N],ne[N<<1],to[N<<1],edgew[N<<1];
void addEdge(int u,int v,int w){to[++tot]=v;ne[tot]=h[u];h[u]=tot;edgew[tot]=w;}
void dfs_getD(int u,int father)
{
fa[u]=father;
if(dis[u]>dis[rt]) rt=u;
for(int i=h[u];i;i=ne[i])if(to[i]!=father)
{
int v=to[i];
dis[v]=dis[u]+edgew[i];
dfs_getD(v,u);
}
}
int si=0,b[N];
int max_dia;
void dfs(int u,int father)//求直径
{
dis[u]=0;
for(int i=h[u];i;i=ne[i])if(to[i]!=father)
{
int v=to[i];
dfs(v,u);
max_dia=max(max_dia,dis[u]+dis[v]+edgew[i]);
dis[u]=max(dis[u],dis[v]+edgew[i]);
}
}
int getTedgewoSubtree_maxDia(int x)
{
max_dia=0;
dfs(b[x],b[x-1]);
int tmpMax=max_dia;
max_dia=0;
dfs(b[x-1],b[x]);
return max(tmpMax,max_dia);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
dis[1] = 0;
dfs_getD(1, 0);
dis[rt] = 0;
dfs_getD(rt, 0);
//直径路径保存到b[]
b[++si] = rt;
while (fa[b[si]] != 0)
b[si + 1] = fa[b[si]], si++;
int ans = INF;
for (int i = si; i > 1; i--)
ans = min(ans, getTedgewoSubtree_maxDia(i));
cout << ans << endl;
} 参考大佬的思路：
https://blog.nowcoder.net/n/53c3058e99364b9fb57bcdd830e4295c
我通俗（小白）的来理解理解大佬的思路……
最重要的一点：删除的一定是直径上的边！
假设不断直径上的边，那么树的直径不变，答案就仍然是那条直径长度
找出树的任意一条直径，让直径的序列为，直径的长度为d，取直径的一半（向上取整，7的话取4）为len，只要在直径序列中找到一个点i满足(dis为一个点到根的距离)b1到bi的距离<=d且
距离也小于等于d，断开
的边，求两个子树直径的最大值就是答案。
如果答案没经过直径上的点呢？？？
假设断掉之后，答案路径没有经过原树直径上的点（答案就是子树直径的最大值），那断开其他边（上面分析了只能断原树直径上的边）只会大于等于答案
如果答案路径经过直径上的点，那么一定是原树直径上的某个点k是LCA(某个子树的某个叶子节点v,
或者
),即v->k->b1/bn这条路径。那么我们就要最小化k->b1/bn的距离，取直径的一半（向上取整）就可以了。。。
感叹一下：卧槽 大佬真强。。。代码加了注释，希望大家都能看懂大佬的思路#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int N=1e6+5; int n,tot,rt,dis[N],fa[N],h[N],ne[N<<1],to[N<<1],edgew[N<<1]; void addEdge(int u,int v,int w){to[++tot]=v;ne[tot]=h[u];h[u]=tot;edgew[tot]=w;} void dfs_getD(int u,int father) { fa[u]=father; if(dis[u]>dis[rt]) rt=u; for(int i=h[u];i;i=ne[i])if(to[i]!=father) { int v=to[i]; dis[v]=dis[u]+edgew[i]; dfs_getD(v,u); } } int si=0,b[N]; int max_dia; void dfs(int u,int father)//求直径 { dis[u]=0; for(int i=h[u];i;i=ne[i])if(to[i]!=father) { int v=to[i]; dfs(v,u); max_dia=max(max_dia,dis[u]+dis[v]+edgew[i]); dis[u]=max(dis[u],dis[v]+edgew[i]); } } int getTedgewoSubtree_maxDia(int x) { max_dia=0; dfs(b[x],b[x-1]); int tmpMax=max_dia; max_dia=0; dfs(b[x-1],b[x]); return max(tmpMax,max_dia); } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,w;scanf("%d%d%d",&u,&v,&w); addEdge(u,v,w);addEdge(v,u,w); } dis[1]=0; dfs_getD(1,0); dis[rt]=0; dfs_getD(rt,0); int len=dis[rt]/2+dis[rt]%2; //直径路径保存到b[] b[++si]=rt; while(fa[b[si]]!=0) b[si+1]=fa[b[si]],si++; for(int i=si;i>1;i--) if(dis[b[i]]<=len&&dis[rt]-dis[b[i-1]]<=len) { printf("%d\n",getTedgewoSubtree_maxDia(i)); break; } }
B
耗在了A接近两个小时，结果看了一眼B。。10分钟就做出来了。。还以为A最简单。题目顺序能不坑我吗。。。
结论证明官方题解写的很清楚，就是幂为0分配n个，接下来依次给幂1,2,……分配n-1个，详见代码
证明摘自官方题解https://ac.nowcoder.com/discuss/400742
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ENTER cout<<endl
/***********************************************************/
const int MOD = 1e9+ 7;
const int maxn=1e6+10;
const int MAXN = 1e5 + 10;
/***********************************************************/
int ans[maxn]={0};
signed main(){
int n,x;
ios::sync_with_stdio(false);
cin>>n>>x;
int num=n/x;
int zero=0;
int g_ans=1;
ans[g_ans++]=0;
while(g_ans<n){
for(int j=1;j<=x-1 && g_ans<n;++j){
ans[g_ans++]=zero;
}
zero++;
}
ans[0]=zero;
for(int i=0;i<n;++i){
cout<<ans[i]<<" ";
}
}
