当前位置: 首页 > news >正文

校内模拟赛 路径 题解

题意:

有一棵 n 个节点的无根树(\(n\le 1.6\times 10^5\)),树上第 i 个节点有一个正整数 \(A_i\) 作为点权。有趣的是,这棵无根树度数为 1 的节点不超过 10 个。

请求出一条树上的路径,使得路径上包含的节点个数乘以路径经过点权的最大公约数最大。

题解:

方法一:

乱搞,由于一个数的因数是 \(\sqrt n\) 左右的,所以我们可以把每一个叶子拎出来,用 map 维护对于这个子树,经过自己且自己为一个链的端点的所有可能的答案。我们不可能数漏,因为把每一个叶子拎起来的过程就对应了一种成链方向,而枚举所有叶子可以保证每一条可能的答案都至少形成一次祖先子树关系。复杂度 \(O(10n\sqrt n)\) 左右,跑不满。

code:

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define umap unordered_map
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=2e5+10;
int n,m,k,T,a[N],d[N],ans;
umap<int,int> mp[N];
vector<int> g[N];
void dfs(int u,int fa){for(int v:g[u]){if(v==fa) continue;dfs(v,u);for(auto t:mp[v]){int x=__gcd(a[u],t.fi);mp[u][x]=max(mp[u][x],t.se+1);ans=max(ans,x*t.se+1);}mp[v].clear();}mp[u][a[u]]=max(mp[u][a[u]],1ll);ans=max(ans,a[u]*mp[u][a[u]]);
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;rep(i,1,n){cin>>a[i];	}rep(i,1,n-1){int u,v;cin>>u>>v;d[u]++;d[v]++;g[u].pb(v);g[v].pb(u);}rep(i,1,n){if(d[i]==1){dfs(i,0);ans=max(ans,a[i]*mp[i][a[i]]);mp[i].clear();}}cout<<ans;return 0;
}

方法二:

思考链的情况,其实就是JSOI2015] 最大公约数 - 洛谷,复杂度 \(O(n\log^2n)\) 我们考虑延续这种做法,发现我们可以把任意两个叶子的路径组成一条链,答案一定在这之中,总复杂度\(O(45n\log^2 n)\)

细节:用 dfs 序 \(+\) 栈 维护这条路径上的点比较方便。不要乱用 \(long~long\)\(T\)

code:

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=2e5+10;
int n,m,k,T,a[N],f[N],tmp[N],cnt,dfn[N],idx[N],top[N];
int hson[N],siz[N],dep[N],d[N],s[N],tot;
long long ans;
vector<int> g[N];
void dfs1(int u,int fa){f[u]=fa;dep[u]=dep[fa]+1;siz[u]=1;for(int v:g[u]){if(v==fa) continue;dfs1(v,u);siz[u]+=v;if(siz[v]>siz[hson[u]]) hson[u]=v;}
}
void dfs2(int u,int fa){dfn[u]=++tot;idx[tot]=u;if(hson[u]){top[hson[u]]=top[u];dfs2(hson[u],u);}for(int v:g[u]){if(v==fa||v==hson[u]) continue;top[v]=v;dfs2(v,u);}
}
void work(int s,int e){if(s==e){ans=max(ans,(ll)a[idx[tmp[s]]]);return;}int mid=s+e>>1;work(s,mid);work(mid+1,e);int g=a[idx[tmp[mid]]],l=mid,r=mid;while(s<l&&r<=e){g=__gcd(g,a[idx[tmp[--l]]]);while(s<l&&!(a[idx[tmp[l-1]]]%g)) l--;while(r<e&&!(a[idx[tmp[r+1]]]%g)) r++;ans=max(ans,(ll)(r-l+1)*g);}g=a[idx[tmp[mid]]],l=r=mid;while(s<=l&&r<e){g=__gcd(g,a[idx[tmp[++r]]]);while(s<l&&!(a[idx[tmp[l-1]]]%g)) l--;while(r<e&&!(a[idx[tmp[r+1]]]%g)) r++;ans=max(ans,(ll)(r-l+1)*g);}
}
void mak(int x,int y){stack<pii>st1,st2;cnt=0;int tag=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y),tag^=1;if(tag==0) st1.push({dfn[top[x]],dfn[x]});else st2.push({dfn[top[x]],dfn[x]});x=f[top[x]];}if(dep[x]>dep[y]) swap(x,y);st1.push({dfn[x],dfn[y]});while(!st1.empty()){pii l=st1.top();st1.pop();per(i,l.se,l.fi) tmp[++cnt]=i;}while(!st2.empty()){pii l=st2.top();st2.pop();rep(i,l.fi,l.se) tmp[++cnt]=i;}work(1,cnt);
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;rep(i,1,n) cin>>a[i];rep(i,1,n-1){int u,v;cin>>u>>v;d[u]++;d[v]++;g[u].pb(v);g[v].pb(u);}dfs1(1,0);top[1]=1;dfs2(1,0);tot=0;rep(i,1,n) if(d[i]==1) s[++tot]=i;rep(i,1,tot)rep(j,i+1,tot)mak(s[i],s[j]);cout<<ans;return 0;
}

方法三(官方写法):

注意到只有 \(10\)个叶子节点,所以我们依此从这 \(10\)个叶子节点开始 DFS。 并且可以发现对于一个串从左往右做前缀gcd,最多只有 \(O(logV)\)个不同的值。 所以我们维护分界点的位置和值,然后对于在串的开头增加一个数字,我们可以\(O(logV)\) 暴力更新我 们维护的位置和值。 所以每次DFS的时候,从上往下DFS,并且维护每个点到根节点的路径上的\(O(logV)\) 个分界点即可。 最终复杂度\(O(10nlogV)\)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;
}
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=160010;
int n,fa[maxn],val[maxn],first[maxn],nxt[maxn<<1],to[maxn<<1],deg[maxn],e;
void AddEdge(int u,int v) {to[++e]=v;nxt[e]=first[u];first[u]=e;to[++e]=u;nxt[e]=first[v];first[v]=e;deg[u]++;deg[v]++;
}
ll ans;
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
ll dep[maxn];
struct Data {int n;pii a[35];
}D[maxn];
void dfs(int x) {D[x]=D[fa[x]];dep[x]=dep[fa[x]]+1;D[x].a[++D[x].n]=mp(x,val[x]);rep(i,1,D[x].n) {D[x].a[i]=mp(D[x].a[i].xx,gcd(D[x].a[i].yy,val[x]));ans=max(ans,D[x].a[i].yy*(dep[x]-dep[fa[D[x].a[i].xx]]));}int cnt=0;rep(i,1,D[x].n) if(D[x].a[i].yy!=D[x].a[i-1].yy) D[x].a[++cnt]=D[x].a[i];D[x].n=cnt;for(int i=first[x];i;i=nxt[i]) if(to[i]!=fa[x]) fa[to[i]]=x,dfs(to[i]);
}
int main() {n=read();rep(i,1,n) val[i]=read();rep(i,2,n) AddEdge(read(),read());rep(i,1,n) if(deg[i]==1) fa[i]=0,dfs(i);printf("%lld\n",ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=21474

相关文章:

  • 05-FreeRTOS的内存管理
  • 2025攻丝机品牌最新权威推荐排行榜:聚焦全自动攻丝机,半自动等机型,精选攻丝机实力厂商助企业高效选购
  • 软件测试覆盖率详解
  • oppoR9m刷Linux系统: 说明-注意事项-知识点
  • 手机框架材质
  • 2025年陶瓷定制企业最新推荐榜单:涵盖电子陶瓷,氧化铝陶瓷,氧化锆陶瓷,氮化铝陶瓷,结构陶瓷领域!
  • 2025阳台装修品牌推荐榜:优质阳台厂商资质、技术、服务测评及高口碑企业优选指南,浙江多为建筑服务与性价比兼具!
  • 2025 年杭州小程序开发机构最新推荐榜单:覆盖多行业定制需求,助力企业精准选靠谱服务商
  • 2025年杭州软件开发公司最新品牌推荐榜:聚焦技术实力与售后体系的优质服务商精选指南!
  • 2025 年独立游戏公司 TOP 设计平台推荐排行榜,独立游戏开发 / 美术 / 原画 / 素材 / 设计 / 角色 / 场景 / 道具 / UI / 策划 / 独立像素游戏公司推荐
  • 湖南省茶陵一中校庆120周年:205班捐款
  • 实用指南:计算机网络-ipv4首部校验原理
  • 2025 年人工智能培训厂家最新推荐排行榜:聚焦人工智能培训合规运营机构、产业适配能力与教学实力深度解析
  • 一种以125kHz低频识别 + 2.4GHz数据传输”的方案,通过频率优势互补,为近距离物联网应用提供了可靠、精准且高效的解决方案
  • 高效做PPT!5个亲测模板网站,10分钟出专业演示 !
  • 【WCH蓝牙系列芯片】-基于CH592开发板——HID_Keyboard中添加读、写、通知的服务属性
  • 2025 年 AI 健康管理厂商最新推荐榜单:覆盖多场景需求,深护智康等优质品牌助力行业升级
  • 虚幻5.6插件添加自定义shader
  • 在线考试小程序管理系统:一站式智能考试解决方案,助力多场景高效考核
  • 快微商城小程序管理系统:助力商家搭建高效便捷的新零售平台
  • 2025最新布袋包装厂家推荐排行榜:布袋包装,布袋,手提袋,帆布袋定制,无纺布袋,布袋生产,云南布袋包装,茶叶布袋生产商优选指南
  • KTV 娱乐小程序管理系统:数字化运营新选择,助力行业高效经营
  • 城市电商小程序管理系统:助力商家搭建全渠道数字化经营体系
  • oppoR9m刷Linux系统: ColorOS系统OTA卡刷降级系统版本
  • 深入解析:[免费]基于Python的在线音乐网站系统(后端Django)【论文+源码+SQL脚本】
  • 勒索软件速度危机:AI驱动下的网络安全新挑战
  • 2025沈阳标识标牌厂家推荐排行榜:聚焦行业产能与技术实力,精选沈阳标识标牌优质企业供订做参考
  • Oracle故障分析:数据库不能open下查看undo段的名字
  • 实用指南:智慧外贸平台|基于Java+vue的智慧外贸平台系统(源码+数据库+文档)
  • L04_新建springboot项目与新建helloword(菜鸟版)