恒生电子

题目：无环树求所有路径最大值的和笔试的时候没写出来，想到了边权按贡献算，但只写了个暴力20%。正解：并查集每个点视为一个联通块，先按边权从小到大排序，逐个加入边。联通块里的值肯定都小于当前边权，那么左右联通块大小就分别代表边左右两侧的节点数，相乘就是路径数。所以贡献 = 左边连通块大小 × 右边连通块大小 × 边权。代码如下struct edge {int u, v, w;edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}bool operator<(const edge &other) const { return w < other.w; }};ll res = 0, n;vector<edge> e;int fa[N], sz[N];int find(int x) { return fa[x] = ((fa[x] == x) ? x : find(fa[x])); }void unite(int x, int y) {int rx = find(x), ry = find(y);if (rx == ry)return;if (sz[rx] < sz[ry])swap(rx, ry);fa[ry] = rx, sz[rx] += sz[ry];}void solve() {cin >> n;for (int i = 1; i < n; i++) {int u, v, w;cin >> u >> v >> w;e.emplace_back(u, v, w);}for (int i = 1; i <= n; i++) {fa[i] = i, sz[i] = 1;}sort(e.begin(), e.end());for (const auto &e : e) {int ru = find(e.u);int rv = find(e.v);if (ru != rv) {// 贡献 = 左边连通块大小 × 右边连通块大小 × 边权res = (res + (ll)sz[ru] * sz[rv] % mod * e.w % mod) % mod;unite(e.u, e.v);}}cout << res << endl;}

📍面试公司：神州信息🕐面试时间：3.15 26届双非本，后端岗💻面试岗位：后端开发❓面试问题：hr：实习收获实习最大困难，怎么解决的学到了什么工作意向地点技术：你写的东西，哪块是你做的（有点绷不住了，虽然你我都知道实习生打杂，但第一次这么直白的我还是第一次见）难点jdk21新特性策略模式设计模式是拿来解决什么问题的（为啥要用，不用行不行）线程池参数🙌面试感想：应该就是海面，还是第一次见hr跟技术一起来的，方便筛人是吧时长就不到半小时，也是很快啊。啪的一下就结束了前面做了笔试，笔试的话应该还算可以

笔试时间跟家里的一些事情冲突了能改一下时间嘛我找不到联系方式啊😭😭

时长1个小时一道算法题：设计一个栈，要求能以o(1)的时间获得栈的最小值，十五分钟，太久没写算法了，没a出来，不过面试官说我的思路是对的。一道数学题：25批马，5个赛道，用最少得次数获得前三名。一道场景题：设计一个ip黑地址系统问了ai的mcp的原理和rag的原理面试官还挺好的，不会的话会尝试去引导你写出来没问八股可能是涉及到转技术栈，说要转go自我感觉应该是够呛吧，白背好几天八股