坠机：P15370 『ICerOI Round 1』这是兔兔，她很可爱 / [SNOW] - 74
fish_love_cat · · 题解
:::info[什么样的人生是失败的？（第六弹）] 点击标题可以看见上一次坠机。
话说这是一篇咕了有点时间的题解。
赛时写的正解刚刚才通过，怎么回事呢。
吸取教训，正开。
话说我怎么被 T1 卡了，有点笨蛋。
然后 T2 偶遇位运算分讨大题，拼尽全力终于战胜。
T3 一眼瞪出思路，发现巨大 ds 但是还剩 2h，优势在我！
距离比赛结束还剩 10min 极限写完！
赢了……被卡常了。
想说的话很多，但处于谨言慎行的考虑那还是什么都不说了。不过我有一个引用在这里会很难绷的句子。应该和这场比赛没有关系，我说真的。
摘自 Iwa 大神对某个除夕 unr 比赛的评语。 :::
250pts 遗憾离场。
为什么会变成这样子呢？我问出题人。
只考虑一个路径的话那肯定是一段上升后一段下降。
考虑把路径上的边断开，那么变成若干个连通块，显然的一个连通块内符合条件的点的数量就是这个连通块内路径上的点的权值。
于是现在你需要找到前缀权值和恰好跨越
并不是很好做。
观察到这个前缀在上升段的时候等价于子树大小。
只考虑一路上升的话，我们只需要维护子树内
显然我们并不需要维护每个点，这个东西有单调性，我们只需要倍增的去求解就行。
那怎么快速求解这个东西呢？套路的考虑树剖。
把树压扁到序列上考虑，然后变成求区间内
具体的，我们按照值的顺序在区间上进行加点，于是一个树上就可以求出
于是我们可以用
考虑存在下降段怎么做。
你突然发现下降段是可以处理后缀和的，于是把题目变形一下就好。
注意不要把 LCA 混进去算，如果上升段查找失败下降段也查找失败，那么答案就是 LCA 了。
于是时间复杂度
倍增的时候可以记录深度然后与 LCA 的深度进行比较，减少在主席树上的查询次数，这个剪枝可以快很多。
唯一难点在于卡常。
#include<bits/stdc++.h>
#define int unsigned int
#define N 200005
using namespace std;
struct fish{
int nex,t,w;
}A[500005];
int head[N],tp;
void add(int u,int v,int w){
A[++tp].nex=head[u];
A[tp].t=v;
A[tp].w=w;
head[u]=tp;
}
inline char get_char(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
int sum=0,fish=1;
char c=get_char();
while((c<'0'||c>'9')&&c!='-')c=get_char();
if(c=='-')fish=-1,c=get_char();
while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=get_char();
return sum*fish;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else print(x/10),putchar(x%10+'0');
}
struct node{
int x,ls,rs;
};
int a[N];
int rt[N];
struct his_tr{
node tr[(N<<5)+10];
int top=0;
int cop(int x){
int ret=++top;
tr[ret]=tr[x];
return ret;
}
void pushup(int x){
tr[x].x=tr[tr[x].ls].x+tr[tr[x].rs].x;
}
int upd(int x,int l,int r,int t){
x=cop(x);
if(t<=l&&r<=t){
tr[x].x++;
return x;
}
int mid=(l+r)>>1;
if(t<=mid)tr[x].ls=upd(tr[x].ls,l,mid,t);
else tr[x].rs=upd(tr[x].rs,mid+1,r,t);
pushup(x);
return x;
}
int qry(int x,int y,int l,int r,int L,int R){
if(L<=l&&r<=R){
return tr[x].x-tr[y].x;
}
int mid=(l+r)>>1;
int ret=0;
if(L<=mid)ret+=qry(tr[x].ls,tr[y].ls,l,mid,L,R);
if(mid<R)ret+=qry(tr[x].rs,tr[y].rs,mid+1,r,L,R);
return ret;
}
}tr;
int dfn[200005],top;
int mx[200005];
int f[200005][20];
int n,m;
int mi[25][200005];
int dep[200005];
int get(int u,int v){
if(dfn[u]>dfn[v])return v;
return u;
}
int lca(int u,int v){
if(u==v)return u;
u=dfn[u],v=dfn[v];
if(u>v)swap(u,v);
int g=__lg(v-u);
return get(mi[g][u+1],mi[g][v-(1<<(g))+1]);
}
void dfs(int x,int fa){
f[x][0]=fa;
dfn[x]=++top;
a[top]=x;
dep[x]=dep[fa]+1;
mi[0][dfn[x]]=fa;
for(int i=head[x];i;i=A[i].nex){
int v=A[i].t;
if(v==fa)continue;
dfs(v,x);
}
mx[x]=top;
}
int qry(int x,int l,int r){
return tr.qry(rt[mx[x]],rt[dfn[x]-1],1,n,l,r);
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0),cout.tie(0);
n=read(),m=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
add(u,v,0);
add(v,u,0);
}
dfs(1,0);
for(int i=1;i<=n;i++)
rt[i]=tr.upd(rt[i-1],1,n,a[i]);
for(int i=1;i<20;i++)
for(int j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
for(int i=1;i<20;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
mi[i][j]=get(mi[i-1][j],mi[i-1][j+(1<<(i-1))]);
int ans=0;
int l,r,u,v,k;
while(m--){
l=read()^ans,r=read()^ans,u=read()^ans,v=read()^ans,k=read()^ans;
int p=lca(u,v);
int mx=qry(p,l,r);
for(int i=19;i>=0&&i<=19;i--)
if(f[u][i]&&dep[f[u][i]]>=dep[p]){
int chk=qry(f[u][i],l,r);
if(chk>=mx)continue;
if(chk<k)u=f[u][i];
}
if(u!=p&&qry(u,l,r)>=k){
ans=u;
print(ans);
puts("");
continue;
}else if(f[u][0]&&f[u][0]!=p&&qry(f[u][0],l,r)>=k&&u!=p){
ans=f[u][0];
print(ans);
puts("");
continue;
}
k=r-l+1-k+1;
for(int i=19;i>=0&&i<=19;i--)
if(f[v][i]&&dep[f[v][i]]>=dep[p]){
int chk=qry(f[v][i],l,r);
if(chk>=mx)continue;
if(chk<k)v=f[v][i];
}
if(qry(v,l,r)>=k){
ans=v;
print(ans);
puts("");
continue;
}else if(f[v][0]&&f[v][0]!=p&&qry(f[v][0],l,r)>=k&&v!=p){
ans=f[v][0];
print(ans);
puts("");
continue;
}
ans=p;
print(ans);
puts("");
}
return 0;
}
// 第一次看到你的那一天，我在面包店看到了一件怪事。
// 一个头戴兜帽的女孩子，从口袋里拿出一堆死虫想买面包。
// 那一幕非常诡异。
// 女孩说死虫是「钱」。
// 她跟一脸困扰、用温柔语气和她解释死虫不能买面包的老板说了几句话后，就露出大受打击的神情跑出店门口。