3 条题解
-
28
主播主播，你的树剖确实强悍，但是太难操作了，有没有算法简单，而且时间复杂度还优的做法呢？
有的兄弟，有的，这里是一篇单 的题解！
考虑并查集啊，只需要维护树上每个节点向上走，离它最近的没被走过的节点就好了。
你发现你每次向上跳只会跳没被走过的点，于是每个点至多被跳到一次，所以时间复杂度是 的。
#include <iostream> #include <vector> #define ll int using namespace std; const ll M=4e5+10; const ll N=5e5+10; inline void read(ll &x){ x=0;bool flag(0);char ch=getchar(); while(!isdigit(ch)) flag=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); flag?x=-x:0; } ll dep[N],zg[N],stt; ll findf(ll x){ if(zg[x]==x) return x; return zg[x]=findf(zg[x]); } void _merge(ll x,ll y){ ll fx=findf(x),fy=findf(y); if(fx!=fy) zg[fy]=fx; } ll fa[N][20],n,m,lin[M]; vector<ll> A[N]; void init(){for(ll i=1;i<=n;i++) zg[i]=i;} void dfs(ll u,ll f){ fa[u][0]=f;dep[u]=dep[f]+1; for(ll i=1;i<20;i++){ fa[u][i]=fa[fa[u][i-1]][i-1]; if(fa[u][i]==0) break; } ll rt=A[u].size(); for(ll i=0;i<rt;i++){ if(A[u][i]==f) continue; dfs(A[u][i],u); } } ll lca(ll a,ll b){ if(dep[a]<dep[b]) swap(a,b); for(ll i=19;i>=0;i--) if(dep[fa[a][i]]>=dep[b]) a=fa[a][i]; if(dep[a]>dep[b]) a=fa[a][0]; for(ll i=19;i>=0;i--) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i]; if(a!=b) a=fa[a][0],b=fa[b][0]; return a; } bool vis[N]; void biaoji(ll from,ll to){ ll now=from; while(dep[now]>=dep[to]){ vis[now]=1; ll nxt=fa[findf(now)][0]; _merge(to,now); now=nxt; } } int main(){ read(n),read(m),read(stt); init(); for(ll i=1;i<n;i++){ ll x,y; read(x),read(y); A[x].push_back(y); A[y].push_back(x); } for(ll i=1;i<=m;i++) read(lin[i]); dfs(1,0); long long ans=0; vis[stt]=1; for(ll i=1;i<=m;i++){ if(vis[lin[i]]) continue; ll lc=lca(stt,lin[i]); vis[stt]=vis[lc]=vis[lin[i]]=1; ans+=(dep[stt]-dep[lc])+(dep[lin[i]]-dep[lc]); biaoji(stt,lc); biaoji(lin[i],lc); stt=lin[i]; } cout<<ans; return 0; } -
-31
题意
给你一个n个点的树
你现在在s点
你需要按照顺序走到指令序列的位置，如果之前已经到达就不去
正解
我们可以将这颗树剖一下
然后每次跳重链，然后用树状数组维护已经去的点，就做完了
code
#include <bits/stdc++.h> using namespace std; inline long long R() { long long x = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } inline void W(long long x) { if(x < 0) { x = -x; putchar('-'); } if(x > 9) W(x/10); putchar(x%10+'0'); } const long long N = 5e5 + 10; long long s, m, n; vector<long long> e[N]; long long fa[N], son[N], dep[N], sz[N], top[N], dfn[N], dfncnt; void clear() { } void read() { n = R(); m = R(); s = R(); for(long long i = 1; i < n; i++) { long long u = R(); long long v = R(); e[u].push_back(v); e[v].push_back(u); } return ; } void dfs1(long long u,long long f) { fa[u] = f; dep[u] = dep[f] + 1; sz[u] = 1; for(long long v : e[u]) { if(v == f) continue; dfs1(v,u); sz[u] += sz[v]; if(!son[u] || sz[son[u]] < sz[v]) son[u] = v; } return ; } void dfs2(long long u,long long t) { top[u] = t; dfn[u] = ++dfncnt; if(!son[u]) return ; dfs2(son[u],t); for(long long v : e[u]) { if(v == fa[u] || v == son[u]) continue; dfs2(v,v); } } long long w[N]; long long lb(long long x) { return x & (-x); } void add(long long i,long long x) { for(; i <= n; i += lb(i)) w[i] += x; } long long qry(long long i) { long long res = 0; for(; i; i -= lb(i)) res += w[i]; return res; } void upd(int l,int r){ if(l > r) swap(l,r); add(l,1); add(r+1,-1); } long long update(long long u,long long v) { long long ans = 0; while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u,v); upd(dfn[top[u]],dfn[u]); ans += dfn[u] - dfn[top[u]] + 1; u = fa[top[u]]; } if(dfn[u] > dfn[v]) swap(u,v); upd(dfn[u],dfn[v]); return ans + dfn[v] - dfn[u]; } void compute() { dfs1(1,0); dfs2(1,1); long long now = s; update(now,now); long long ans = 0; for(long long i = 1; i <= m; i++) { long long v = R(); if(!qry(dfn[v])) { ans += update(now,v); now = v; } } W(ans); } void init() { } int main() { clear(); read(); init(); compute(); return 0; }upd
这里放一下我的对拍
checker：
while(1){ system("gen.exe"); system("bl.exe"); system("code.exe"); if(system("fc a.out a.ans")){ return 0; } }baoli:
#include <bits/stdc++.h> using namespace std; inline int R(){ int x = 0, f = 1; char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)){ x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } inline void W(int x){ if(x < 0){ x = -x; putchar('-'); } if(x > 9) W(x/10); putchar(x%10+'0'); } const int N = 5e5 + 10; int n, m, s; vector<int> e[N]; void clear(){ } void read(){ n = R(); m = R(); s = R(); for(int i = 1;i < n; i++){ int u, v; u = R(); v = R(); e[u].push_back(v); e[v].push_back(u); } return ; } int dep[N], fa[N], vis[N]; void dfs(int u,int f){ dep[u] = dep[f] + 1; fa[u] = f; for(int v : e[u]){ if(f == v) continue; dfs(v,u); } } int get(int u,int v){ int ans = 0; if(dep[v] > dep[u]) swap(u,v); while(dep[u] > dep[v]){ vis[u] = 1; u = fa[u]; ans++; } while(u != v){ vis[u] = 1; vis[v] = 1; u = fa[u]; v = fa[v]; ans += 2; } vis[u] = 1; return ans; } void compute(){ dfs(1,0); int now = s; vis[s] = 1; int ans = 0; for(int i = 1;i <= m; i++){ int v = R(); if(!vis[v]){ ans += get(now,v); now = v; } } cout << ans; } void init(){ } int main(){ freopen("a.in","r",stdin); freopen("a.ans","w",stdout); clear(); read(); init(); compute(); return 0; }gen:
int ra(int n){ return (rand() * rand()) % n; } int main(){ freopen("a.in","w",stdout); srand(time(0)); int n = 10, m = 5, s = 2; cout << n << ' ' << m << ' ' << s << '\n'; for(int i = 2;i <= n; i++){ cout << i << ' '; cout << ra(i-1) + 1 << '\n'; } for(int i = 1;i <= m; i++){ cout << ra(m-1)+1 << ' '; } return 0; }-
Dygram_Dxi @ 2025-3-25 16:28:50
这看起来是 的，鉴定为数据太水了
-
Dygram_Dxi
LV 6
@ 2025-3-25 16:35:05
- 1
