1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; int (){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; } struct Edge{ int v,_next; }; Edge edge[200005]; int cnt=0,at[100005]={0}; int fa[100005],son[100005]={0},siz[100005],top[100005], depth[100005],pos[100005],fp[100005],val[100005]; int S,nows=0,n,m,_a,_b,C[400005]; int lowbit(int x){ return x&(-x); } void update(int k,int v){ while(k<=S)C[k]+=v,k+=lowbit(k); } int query(int r){ int res=0; while(r)res+=C[r],r-=lowbit(r); return res; } void addedge(int _u,int _v){ edge[++cnt].v=_v, edge[cnt]._next=at[_u], at[_u]=cnt; } void dfs1(int x,int par,int d){ depth[x]=d,fa[x]=par,siz[x]=1; for(int i=at[x];i;i=edge[i]._next){ if(edge[i].v==par)continue; int _v=edge[i].v; dfs1(_v,x,d+1); siz[x]+=siz[_v]; if(!son[x]||siz[_v]>siz[son[x]]) son[x]=_v; } } void dfs2(int x,int tp){ top[x]=tp,pos[x]=++nows,fp[nows]=x; if(!son[x])return; dfs2(son[x],tp); for(int i=at[x];i;i=edge[i]._next) if(edge[i].v!=fa[x]&&edge[i].v!=son[x]) dfs2(edge[i].v,edge[i].v); } void update_tr(int u,int v){ while(top[u]!=top[v]){ if(depth[top[u]]<depth[top[v]]) swap(u,v); update(pos[top[u]],1); update(pos[u]+1,-1); u=fa[top[u]]; } if(depth[u]<depth[v])swap(u,v); if(u==v)return ; v=son[v]; update(pos[u]+1,-1); update(pos[v],1); } int query_tr(int u,int v){ if(depth[u]<depth[v])swap(u,v); return query(pos[u]); } void init(){ n=read(),m=read(); for(S=1;S<=n;S<<=1); int u,v; for(int i=1;i<n;i++){ u=read(),v=read(); addedge(u,v),addedge(v,u); } dfs1(1,0,1); dfs2(1,1); } void solve(){ char ord[3]; int x,y; while(m--){ scanf("%s%d%d",ord,&x,&y); if(ord[0]=='P')update_tr(x,y); else printf("%dn",query_tr(x,y)); } } int main(){ init(); solve(); return 0; }
|
近期评论