SPOJ Count on a tree

2019-11-08 18:21:29

字體：大中小

來源：轉載

供稿：網友

題意：

給一棵樹和點權，查詢鏈上第k大點權

解：

主席樹

每個點相對父親的線段樹再加一個點建立主席樹，

查詢的數字出現情況即為t[u]+t[v]-t[lca]-t[fa[lca]]

代碼

#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<queue>#define For(i,j,k) for(int i=(j);i<=(int)k;i++)#define Forr(i,j,k) for(int i=(j);i>=(int)k;i--)#define Set(a,b) memset(a,b,sizeof(a))#define Rep(i,u) for(int i=Begin[u],v=to[i];i;i=Next[i],v=to[i])#define L(i) (T[i].s[0])#define R(i) (T[i].s[1])#define S(i) (T[i].sum)using namespace std;#define ll intconst int N=100010;ll Begin[N],to[N<<1],Next[N<<1],e;ll V[N];inline void add(ll x,ll y){ to[++e]=y,Next[e]=Begin[x],Begin[x]=e;}ll dep[N],fa[N][21];void dfs(int u){ Rep(i,u) if(!dep[v]) dep[v]=dep[u]+1,fa[v][0]=u,dfs(v);}inline void st_init(int n){ For(i,1,20) For(j,1,n) fa[j][i]=fa[fa[j][i-1]][i-1];}inline ll Query(int x,int y){ if(dep[x]<dep[y])swap(x,y); ll d=dep[x]-dep[y]; for(int i=0;(1<<i)<=d;i++) if(d&(1<<i)) x=fa[x][i]; if(x==y)return x; Forr(i,20,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0];}struct A{ ll id,x; bool Operator < (const A b)const { return x<b.x; }};struct node{ ll s[2],sum;};struct tcht{ node T[N*20]; ll rk[N],rt[N],cnt,n; A a[N]; #define mid ((l+r)>>1) inline void init(ll num){ n=num,cnt=0; For(i,1,n)a[i].x=V[i],a[i].id=i; sort(a+1,a+n+1); For(i,1,n)rk[a[i].id]=i; dfs(1,0); } void dfs(ll u,ll f){ insert(rk[u],rt[u]=rt[f],1,n); Rep(i,u) if(v!=f) dfs(v,u); } void insert(ll val,ll &x,ll l,ll r){ T[++cnt]=T[x],x=cnt,++S(x); if(l==r)return ; if(val<=mid)insert(val,L(x),l,mid); else insert(val,R(x),mid+1,r); } ll query(ll u,ll v,ll k){ ll lca=Query(u,v); return a[query(rt[u],rt[v],rt[lca],rt[fa[lca][0]],1,n,k)].x; } ll query(ll u,ll v,ll lca,ll flca,ll l,ll r,ll k){ ll sum=S(L(u))+S(L(v))-S(L(lca))-S(L(flca)); if(l==r)return l; if(k<=sum)return query(L(u),L(v),L(lca),L(flca),l,mid,k); else return query(R(u),R(v),R(lca),R(flca),mid+1,r,k-sum); }}t;int main(){ ll n,m; scanf("%lld%lld",&n,&m); For(i,1,n)scanf("%lld",&V[i]); For(i,1,n-1){ ll u,v; scanf("%lld%lld",&u,&v); add(u,v),add(v,u); } dep[1]=1; dfs(1); st_init(n); t.init(n); For(i,1,m){ ll u,v,k; scanf("%lld%lld%lld",&u,&v,&k); ll ans=t.query(u,v,k);