小米SRE时间线+面经

#淘天笔试# #淘天# #笔试# 考虑换根DP，先随便找个点做根，每个点只统计这个有根树下它的子树对它的贡献，也就是if(color[u] != color[v]) color[u] += color[v];这样我们只能统计出子树的贡献，我们还需要父亲的贡献，父亲的贡献我们考虑扩展并查集，在dfs过程中顺便合并一下就能够得到每个点所在并查集的size，如果一个点和它的父亲不同颜色，那么就是相同并查集，直接用并查集size减去dp求出的子树贡献就是父亲的贡献，然后第二遍dfs，把每个点任意一种颜色都试一下，我们提前知道子树的贡献是多少，可以根据现在我们变的颜色统计一下现在的子树和，看看父亲跟他现在是不是一个颜色，是的话不加贡献，不然加上贡献，和ans取最大值即可。代码如下：#include# include#include# include#include# include#include# include#include# include#include# include#includeusing ll = long long;using ull = unsigned long long;const int maxn = 1e6 + 5;int fa[maxn],sum[maxn],siz[maxn];std::string color;char col[] = {'R','G','B'};int ans  = 0;int find(int x){    return x == fa[x] ? x : find(fa[x]);}void merge(int x,int y){    x = find(x), y = find(y);    if(x == y) return;    siz[x] += siz[y];    fa[y] = x;}std::vector g[maxn];void dfs(int u,int fa){    sum[u] = 1;    for(int i = 0;i < g[u].size();i++){        int v = g[u][i];        if(v == fa) continue;        dfs(v,u);        if(color[u] == color[v]){            sum[u] += sum[v];            merge(u,v);        }    }}void dfs2(int u,int fa){    int sfa = (find(u) == find(fa)) ? siz[find(u)] - sum[u] : siz[find(fa)];    for(int i = 0;i < 3;i++){        char c = col[i];        int s = 1;        for(auto& v : g[u]){            if(v == fa) continue;            if(c != color[v]) s += sum[v];        }        if(c != color[fa]) s += sfa;        ans = std::max(ans,s);    }    for(auto& v: g[u]){        if(v == fa) continue;        dfs2(v,u);    }}void solve(){    int n;    std::cin >> n;    std::cin >> color;    for(int i = 1;i <= n;i++){        siz[i] = 1;        fa[i] = i;    }    for(int i = 0;i < n - 1;i++){        int u,v;        std::cin >> u >> v;        g[u].push_back(v);        g[v].push_back(u);    }    dfs(1,0);    dfs2(1,0);    std::cout << ans << '\n';}int main() {    int T;    T = 1;    while(T--) solve();    return 0;}

真实工作体验，分享给想进游戏厂得学弟学妹~✔️游戏行业入门指南： 明确自己想要从事的职位：游戏行业很多岗位都没有专业要求，提前锚定一个职位，再针对性准备要求的专业能力 整理游戏经历：从游戏玩法的角度梳理自己过往的游戏体验，丰富的游戏经历是加分项，对于想要做游戏策划的同学来说，一定要做一些游戏拆解或者游戏设计文档当作品 ✔️初入职场如何进行心态调整： 做好预期管理 有搞砸一切的心态 无论什么时候都不要放弃好好生活 ✔️作为应届生如何在职场快速landing： 快速熟悉业务和团队，了解领导风格：入职初期一般不会有太多任务，可以主动找领导同事要过往的业务资料研读，请教团队&业务架构以及...

发第二轮笔试邮件了，邮件里有两个不同的自测链接，一个编译选项里有rust，另一个没有，想问下参加第一轮笔试的同学编译选项里有没有rust

应该是支付相关方向，记录一下面经。一面-0218自我介绍服务的注册发现流程获取服务列表的并发安全问题如果获取到servicelist后，某台服务不可用了，会怎么样？随机负载均衡如何实现的？熔断器如何实现的限流器如何实现固定窗口的限流算法实现；状态的记录、状态的变更滑动窗口的限流算法实现优惠券的秒杀实现原理：锁的key是什么为什么用redis预先领取+MQ落库如果一个用户同时发起多个请求，可以避免该用户超领吗原子类如何实现的？算法：画出B+树结构一些sql场景，会不会走索引。联合索引在 > 和 >= 的不同岛屿数量二面-0306可能是leader面自我介绍拷打RPC项目介绍 nett...