http://www.cnblogs.com/duoxiao/p/5777644.html 官方题解在这里
其实这道题不难,当初训练的时候不会做说明自己太弱
lazy标记不pushdown就是用lazy表示这个区间整体有哪些加减操作(大区间答案正确,子区间答案需要被所有祖先区间的lazy修正)
#include<bits/stdc++.h> using namespace std;
struct way{int po,next;} e[];
struct node{int laz,l,r,s,mx,mi;} tr[*];
struct qst{int l,r;} q[];
int l[],r[],a[],fa[],c[],d[],p[],h[];
int n,len,t,op,ans,qq,m; bool cmp(int a,int b)
{
if (l[a]==l[b]) return r[a]<r[b];
return l[a]<l[b];
} void add(int x,int y)
{
e[++len].po=y;
e[len].next=p[x];
p[x]=len;
} void dfs(int x)
{
l[x]=++t; c[t]=x;
for (int i=p[x]; i; i=e[i].next)
{
int y=e[i].po;
if (fa[x]!=y)
{
d[y]=d[x]+;
fa[y]=x;
dfs(y);
}
}
r[x]=t;
} void update(int i,int sz)
{
int l=tr[i].l, r=tr[i].r;
tr[i].s=tr[l].s+tr[r].s+tr[i].laz*sz;
tr[i].mx=max(tr[l].mx,tr[r].mx)+tr[i].laz;
tr[i].mi=min(tr[l].mi,tr[r].mi)+tr[i].laz;
} int build(int l,int r)
{
tr[++t].laz=;
if (l==r)
{
tr[t].mx=tr[t].mi=tr[t].s=d[c[l]];
return t;
}
int m=(l+r)>>,q=t;
tr[q].l=build(l,m);
tr[q].r=build(m+,r);
update(q,r-l+);
return q;
} void work(int i,int sz,int z)
{
tr[i].laz+=z;
tr[i].s+=z*sz;
tr[i].mx+=z;
tr[i].mi+=z;
} int add(int last,int l,int r,int x,int y)
{
tr[++t]=tr[last];
if (x<=l&&y>=r)
{
work(t,r-l+,-);
return t;
}
int m=(l+r)>>,q=t;
if (x<=m) tr[q].l=add(tr[last].l,l,m,x,y);
if (y>m) tr[q].r=add(tr[last].r,m+,r,x,y);
update(q,r-l+);
return q;
} void get(int x)
{
for (int i=p[x]; i; i=e[i].next)
{
int y=e[i].po;
if (fa[x]!=y)
{
h[y]=add(h[x],,n,l[y],r[y]);
work(h[y],n,);
get(y);
}
}
} void ask(int q,int l,int r,int x,int y,int laz)
{
if (op==&&laz+tr[q].mi>=ans) return;
if (op==&&laz+tr[q].mx<=ans) return;
if (x<=l&&y>=r)
{
if (op==) ans+=tr[q].s+(r-l+)*laz;
else if (op==) ans=min(ans,tr[q].mi+laz);
else if (op==) ans=max(ans,tr[q].mx+laz);
return;
}
int m=(l+r)>>;
if (x<=m) ask(tr[q].l,l,m,x,y,laz+tr[q].laz);
if (y>m) ask(tr[q].r,m+,r,x,y,laz+tr[q].laz);
} int main()
{
while (scanf("%d%d",&n,&qq)!=EOF)
{
len=; memset(p,,sizeof(p));
for (int i=; i<n; i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
t=; dfs(); t=;
h[]=build(,n); get();
ans=;
while (qq--)
{
int k,x; bool ff=;
scanf("%d%d%d",&k,&x,&op);
x=(x+ans)%n+;
for (int i=; i<=k; i++) scanf("%d",&a[i]);
if (op==) ans=;
else if (op==) ans=1e9;
else ans=-;
if (!k) {ff=; ask(h[x],,n,,n,);}
else {
sort(a+,a++k,cmp);
q[m=].l=l[a[]]; q[].r=r[a[]];
for (int i=; i<=k; i++)
if (l[a[i]]>q[m].r)
{
q[++m].l=l[a[i]];
q[m].r=r[a[i]];
}
else q[m].r=max(q[m].r,r[a[i]]);
q[m+].l=n+;
int st=, en=q[].l-;
for (int i=; i<=m; i++)
{
if (st<=en) {ff=; ask(h[x],,n,st,en,);}
st=q[i].r+,en=q[i+].l-;
}
if (st<=en) {ff=; ask(h[x],,n,st,en,);}
}
if (!ff) {puts("-1"); ans=;}
else printf("%d\n",ans);
}
}
}