hdu 5756:Boss Bo
题目链接如下：
Problem - 5756
先用dfs确定每个节点的序号编号，并且可以获得每个节点可以包括的子树节点区间范围，再用线段树建立一棵树。
在第一次建立的时候我们记录每个节点的深度，然后再进行一次dfs，这次dfs用来更新以不同节点为根时，距离的维护，利用子树距离减1，非子树距离加1的方法进行更新距离和，最大距离和最小距离。同时不断建立树来打上懒标记，这里打标记的顺序也是dfs的，意味着我们query的时候要进行标记的计算，因为子树并没有更新根节点打上的懒标记。
最后利用补集的方式求出good node 到其余节点的距离。
参考：
hdu 5756(主席树)_top628LJ的博客-CSDN博客
代码如下所示：
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;
#define inf 0x3f3f3f3f
#define MP make_pair
#define mid ((l+r)>>1)
#define pii pair<int,int>
const int MAXN = 100020;
const int MAXM = 500020;
int n,q;
// fst记录一个节点连接的第一条边 vv记录连接到的节点 nxt记录下一条边索引
// fst大小和节点数目一致
int fst[MAXN], vv[MAXM], nxt[MAXM], e;
// st记录节点dfs序的左端点 ed代表右端点 dep表示节点深度 lab表示左端点对应的节点号
int st[MAXN],ed[MAXN],dep[MAXN],lab[MAXN],dc;
// sum mx mi代表和 最大值 最小值 add表示懒标记 ch代表子树位置
int sum[MAXN*50],mx[MAXN*50],mi[MAXN*50],add[MAXN*50],ch[MAXN*50][2];
int rt[MAXN], tot;
pii a[MAXN*5];void init(){memset(fst, -1, sizeof(fst));e=0;
}void adde(int u,int v){vv[e]=v;nxt[e]=fst[u];fst[u]=e++;
}void dfs(int u, int p, int d){dep[u]=d;st[u]=++dc;lab[dc]=u;for (int i = fst[u]; ~i ; i = nxt[i]) {int v = vv[i];if (v == p) continue;dfs(v,u,d+1);}ed[u]=dc;
}void push_up(int l,int r,int rt){int l_rt=ch[rt][0], r_rt=ch[rt][1];sum[rt]=sum[l_rt]+sum[r_rt]+(r-l+1)*add[rt];mx[rt]=max(mx[l_rt], mx[r_rt])+add[rt];mi[rt]=min(mi[l_rt], mi[r_rt])+add[rt];
}int build(int l,int r){int k=++tot;if (l==r){sum[k]=mx[k]=mi[k]=dep[lab[l]]-1;ch[k][0]=ch[k][1]=add[k]=0;return k;}sum[k]=mx[k]=mi[k]=add[k]=0;ch[k][0]=build(l,mid);ch[k][1]=build(mid+1, r);push_up(l,r,k);return k;
}int update(int ul, int ur, int val,int l,int r,int rt){int k=++tot;sum[k]=sum[rt], mx[k]=mx[rt], mi[k]=mi[rt], add[k]=add[rt];ch[k][0]=ch[rt][0], ch[k][1]=ch[rt][1];if (ul==l && ur==r){sum[k]+=(r-l+1)*val;mx[k]+=val;mi[k]+=val;add[k]+=val;return k;}if (ur<=mid) {ch[k][0]=update(ul,ur,val,l,mid,ch[rt][0]);} else if (ul>mid) {ch[k][1]=update(ul,ur,val,mid+1,r,ch[rt][1]);} else {ch[k][0]=update(ul,mid,val,l,mid,ch[rt][0]);ch[k][1]=update(mid+1,ur,val,mid+1,r,ch[rt][1]);}push_up(l,r,k);return k;
}void dfs1(int u,int p){for (int i = fst[u]; ~i ; i=nxt[i]) {int v=vv[i];if (v==p) continue;rt[v]= update(st[v],ed[v],-1,1,n,rt[u]);if (st[v]>1){rt[v]= update(1,st[v]-1,1,1,n,rt[v]);}if (ed[v]<n){rt[v]= update(ed[v]+1,n,1,1,n,rt[v]);}dfs1(v,u);}
}int query(int ul,int ur,int t,int l,int r,int rt){if (ul==l && ur==r){if(t == 1) return sum[rt];else if(t == 2) return mi[rt];else return mx[rt];}if (ur<=mid){int ret = query(ul,ur,t,l,mid,ch[rt][0]);if (t==1) ret+=(ur-ul+1)*add[rt];else ret+=add[rt];return ret;}else if (ul>mid) {int ret = query(ul,ur,t,mid+1,r,ch[rt][1]);if (t==1) ret+=(ur-ul+1)*add[rt];else ret+=add[rt];return ret;}else {int ret1 = query(ul,mid,t,l,mid,ch[rt][0]);int ret2 = query(mid+1,ur,t,mid+1,r,ch[rt][1]);if (t==1) return ret1+ret2+(ur-ul+1)*add[rt];else if (t==2) return min(ret1, ret2)+add[rt];else return max(ret1,ret2)+add[rt];}
}int main(){int u,v;while (~scanf("%d %d", &n, &q)){init();for (int i = 1; i < n; ++i) {scanf("%d %d", &u, &v);adde(u,v);adde(v,u);}dc=0;dfs(1,-1,1);tot=0;rt[1]= build(1,n);dfs1(1,-1);int K,P,T,ans=0,x;while (q--){scanf("%d %d %d",&K,&P,&T);
// cout << "K, P, T:" << K << "," << P << "," << T <<endl;P=(P+ans)%n+1;bool ok= false;for (int i = 1; i <= K; ++i) {scanf("%d",&x);a[i]=MP(st[x],ed[x]);
// cout<<"i:"<<i<<",x:"<<x<<",[st,ed]:"<<"["<<st[x]<<","<<ed[x]<<"]"<<endl;if (x==1){ok=true;}}if (ok){puts("-1"); ans = 0;continue;}sort(a+1,a+1+K);a[++K]=MP(n+1,n+1);if (T==1) ans=0;else if (T==2) ans=inf;else ans=-inf;int pre=1;for (int i = 1; i <= K; ++i) {if (pre<a[i].first){int res = query(pre,a[i].first-1, T,1,n,rt[P]);
// cout<<"In for i:"<<i<<",[st,ed]:"<<"["<<a[i].first<<","<<a[i].second<<"]"<<endl;
// cout << "res:"<<res<<endl;if (T==1) {ans+= res;}else if (T==2) {ans= min(ans,res);}else {ans= max(ans,res);}}pre=max(pre,a[i].second+1);}printf("%d\\n", ans);}}return 0;
}
