3 条题解
-
2
昨天一眼顶针 今天AC
#include <bits/stdc++.h> using namespace std; const int N=110000; int d[N],pos[N],fa[N][20],size[N],c[N],n,m,id; vector<int> e[N]; void dfs(int u,int f) { size[u] = 1; pos[u] = ++id; for(int i=0 ; i < e[u].size(); i++) { int v = e[u][i]; if(v == f) continue; fa[v][0] = u; d[v] = d[u] + 1; dfs(v,u); size[u] += size[v]; } } int lca(int u,int v) { if(d[u] < d[v]) swap(u,v); int de = d[u] - d[v]; for(int i=0; de; de >>= 1,i++) { if(de & 1) u = fa[u][i]; } if(u == v) return v; for(int j=log2(n); j >= 0; j--) { if(fa[u][j] != fa[v][j]) { u = fa[u][j]; v = fa[v][j]; } } return fa[u][0]; } int lowbit(int x) { return x & (-x); } void add(int x,int k) { for(;x <= n ; x += lowbit(x)) { c[x] += k; } } int sum(int x) { int ans = 0; for(; x ; x-=lowbit(x)) { ans += c[x]; } return ans; } int main() { cin >> n >> m; for(int i=1; i < n ;i++) { int u,v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } dfs(1,0); int log2n = log2(n); for(int j=1; j <= log2n ; j++) for(int i=1; i <= n;i++) fa[i][j] = fa[fa[i][j-1]][j-1]; for(int i=1; i <= m;i++) { char op; int u,v; cin >> op >> u >> v; if(op == 'P') { int p = lca(u,v); add(pos[p],-2); add(pos[u],1); add(pos[v],1); } else { if(d[u] < d[v]) swap(u,v); //cout << pos[u]-1 << " " << sum(pos[u]-1) << " " << pos[u] + size[u] -1 << " " << sum(pos[u] + size[u] - 1) << " " ; cout << sum(pos[u] + size[u] - 1) - sum(pos[u] - 1) << endl; } } } -
1
hetao2863173
LV 10
@ 2023-7-23 22:19:27
#include<cstdlib> #include<cstring> #include<cstdio> #include<cctype> #include<algorithm> typedef long long LL; typedef unsigned long long ULL; namespace FastIo{ typedef __uint128_t ULLL; static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw; #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++ inline void pc(const char &ch){ if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw; *pw++=ch; } #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw struct FastMod{ FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){} ULL reduce(ULL a){ ULL q=(ULL)((ULLL(m)*a)>>64); ULL r=a-q*b; return r>=b?r-b:r; } ULL b,m; }HPOP(10); struct QIO{ char ch; int st[40]; inline char read(){ ch=gc; if(ch<'A'||ch>'Z')ch=gc; return ch; } inline void read(int &x){ x=0,ch=gc; while(!isdigit(ch))ch=gc; while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;} } template<class T>inline void write(T a){ do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a); while(st[0])pc(st[st[0]--]^48); pc('\n'); } }qrw; } using namespace FastIo; #define NUMBER1 200000 #define P(A) A=-~A #define fione_i(begin,end) for(register int i=begin;i<=end;P(i)) #define ls(rt) rt<<1 #define rs(rt) rt<<1|1 #define mid (l+r>>1) #define lson l,mid,ls(rt) #define rson mid+1,r,rs(rt) #define sz (r-l+1) #define tt(u) for(register int i=head[u];i;i=e[i].next) struct EDGE{int next,to;}e[(NUMBER1<<1)+5]; int depth[NUMBER1+5],size[NUMBER1+5],son[NUMBER1+5],fa[NUMBER1+5],n,head[NUMBER1+5],tot(0),cnt(0),id[NUMBER1+5],top[NUMBER1+5]; struct Segment{ int tree[(NUMBER1<<2)+5],lazy[(NUMBER1<<2)+5]; inline void push_up(const int &rt){tree[rt]=tree[ls(rt)]+tree[rs(rt)];} inline void change(int l,int r,int rt,int date){tree[rt]+=date*sz,lazy[rt]+=date;} inline void push_down(int l,int r,int rt){ change(lson,lazy[rt]);change(rson,lazy[rt]); lazy[rt]=0; } void intervaland(int l,int r,int rt,int x,int y,int date){ if(x<=l&&r<=y)return tree[rt]+=sz*date,lazy[rt]+=date,void(); if(lazy[rt])push_down(l,r,rt); if(x<=mid)intervaland(lson,x,y,date); if(mid<y)intervaland(rson,x,y,date); push_up(rt); } int intervalsum(int l,int r,int rt,int x,int y){ if(x<=l&&r<=y)return tree[rt]; if(lazy[rt])push_down(l,r,rt); int res(0); if(x<=mid)res+=intervalsum(lson,x,y); if(mid<y)res+=intervalsum(rson,x,y); return res; } }seg; inline void add(const int &u,const int &v){e[++tot].next=head[u];e[tot].to=v,head[u]=tot;} void dfs1(int u,int fath,int deep){ depth[u]=deep,fa[u]=fath,size[u]=1; int ms(-1); tt(u){ if(e[i].to==fath)continue; dfs1(e[i].to,u,deep+1); size[u]+=size[e[i].to]; if(size[e[i].to]>ms)ms=size[e[i].to],son[u]=e[i].to; } } void dfs2(int u,int tf){ id[u]=++cnt,top[u]=tf; if(!son[u])return; dfs2(son[u],tf); tt(u){ if(e[i].to==fa[u]||e[i].to==son[u])continue; dfs2(e[i].to,e[i].to); } } inline void treeand(int x,int y){ while(top[x]!=top[y]){ if(depth[top[x]]<depth[top[y]])std::swap(x,y); seg.intervaland(1,n,1,id[top[x]],id[x],1); x=fa[top[x]]; } if(depth[x]>depth[y])std::swap(x,y); seg.intervaland(1,n,1,id[x],id[y],1); seg.intervaland(1,n,1,id[x],id[x],-1); } inline int treesum(int x,int y){ int ans(0); while(top[x]!=top[y]){ if(depth[top[x]]<depth[top[y]])std::swap(x,y); ans+=seg.intervalsum(1,n,1,id[top[x]],id[x]); x=fa[top[x]]; } if(depth[x]>depth[y])std::swap(x,y); ans+=seg.intervalsum(1,n,1,id[x],id[y]); ans-=seg.intervalsum(1,n,1,id[x],id[x]); return ans; } signed main(){ int m,x,y; char sb; qrw.read(n); qrw.read(m); fione_i(2,n){ qrw.read(x); qrw.read(y); add(x,y);add(y,x); } dfs1(1,0,1); dfs2(1,1); while(m--){ sb=qrw.read(); qrw.read(x); qrw.read(y); if(sb=='P')treeand(x,y); else qrw.write(treesum(x,y)); } fsh; exit(0); return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=100005; int n,m,k,s,t,de[N],tr[N],tot,log2n; int pos[N],sz[N],fa[N][20]; vector<int> e[N]; void dfs(int u){ sz[u]=1;pos[u]=++tot; for (int &v:e[u]){ if (v==fa[u][0]) continue; de[v]=de[u]+1; fa[v][0]=u; dfs(v); sz[u]+=sz[v]; } } int lca(int u,int v){ if (de[u]<de[v]) swap(u,v); for (int i=0,o=de[u]-de[v];o;++i,o>>=1) if (o&1) u=fa[u][i]; if (u==v) return u; for (int j=log2n;j>=0;--j) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j]; return fa[u][0]; } void add(int x,int k){ for (int i=x;i<=n;i+=i&(-i)) tr[i]+=k; } int query(int x){ int ans=0; for (int i=x;i;i-=i&(-i)) ans+=tr[i]; return ans; } int main(){ cin>>n>>m; for (int i=1;i<n;++i){ cin>>s>>t; e[s].push_back(t); e[t].push_back(s); } dfs(1); log2n=log2(n); for (int j=1;j<=log2n;++j) for (int i=1;i<=n;++i) fa[i][j]=fa[fa[i][j-1]][j-1]; char c; int p; for (int i=1;i<=m;++i){ cin>>c; if (c=='P') { cin>>s>>t; p=lca(s,t); add(pos[s],1); add(pos[t],1); add(pos[p],-2); } else { cin>>s>>t; if (de[s]<de[t]) swap(s,t); cout<<query(pos[s]+sz[s]-1)-query(pos[s]-1)<<"\n"; } } }
769147
LV 6
@ 2023-9-23 19:28:29
- 1
