题解 P6071 【[MdOI2020] Treequery】
command_block
·
·
题解
挺有意思的一个题,可以当做树论复习题,特别适合我这种无脑选手练反应。
题意 : 给出一棵无根树,边有边权,点从1开始标号。
多次查询标号在[l,r]的点到p点路径的交集的长度。强制在线。
------------
首先尝试观察性质。注意到这条路径等价$p$到虚树的最短路径,可以帮助思考。
这种树上路径问题,一般要分子树和祖先讨论 :
- (1) $l...r$全部在$p$的子树内
显然,取他们的`LCA`到$p$的距离就好了。其实就是从虚树的根出发。
- (2) $l...r$全部不在$p$的子树内
取虚树上最近的一个点连过来,具体咋搞后面再说。
- (3) $l...r$全部有一部分在$p$的子树内,另一部分不在
显然,得到的虚树包含$p$本身,答案为`0`.
我们可以标号为版本轴,根据`dfs`序建立主席树。
我们就可以差分得到任意$l...r$点集的`dfs`序线段树。
$p$的子树可以表示成一个区间。
把`dfs`序分成三部分 : $L=[1,l),M=[l,r],R=(r,n]$.
首先查看是哪种情况,如果$M$中有元素,而且$L,R$中有元素,则为$(3)$.
如果仅有$M$中有则为$(1)$,否则为$(2)$.
对于$(3)$可以直接得出答案。
对于$(1)$,一个众所周知的结论是 : 点集的`LCA`=`dfs`序最大最小的两个点的`LCA`.
对于$(2)$,需要继续分类讨论。
①路径先上后下
这样子,路径的出发点一定是虚树的根,否则可以更短,我们判一下$p$是否在虚树的根的子树内即可。
②路径直接向下
可以相当于把$p$加入虚树,然后查看到父亲的边的长度。
根据虚树的经典结论,分别查询`dfs`序前驱后继取个`min`即可。
总的来说,写一个`LCA`,再写一个`dfs`序主席树即可,这里只需要求前驱后继。
复杂度$O(n\log n+m\log n)$.
自己`YY`了一种比较好写(?)的方法。
warning : 这份代码包含了很多全局调用,可能导致观看者不适。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pf printf
#define pb push_back
#define MaxN 200500
using namespace std;
inline int read(){
register int X=0;
register char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
int dep[MaxN],dis[MaxN],f[17][MaxN];
vector<int> g[MaxN],l[MaxN];
int in[MaxN],out[MaxN],tp[MaxN],tim;
void pfs(int u)
{
tp[in[u]=++tim]=u;
for (int i=0,v;i<g[u].size();i++)
if (!dep[v=g[u][i]]){
dep[v]=dep[f[0][v]=u]+1;
dis[v]=dis[u]+l[u][i];
pfs(v);
}
out[u]=tim;
}
int lca(int x,int y){
int k=16;
if (dep[y]<dep[x])swap(y,x);
while(k--)
while(dep[f[k][y]]>=dep[x])
y=f[k][y];
k=16;
while(k--)
while(f[k][x]!=f[k][y])
{x=f[k][x];y=f[k][y];}
return x==y ? x : f[0][y];
}
struct Node
{int l,r,c;}a[MaxN*20];
int n,tn,rt[MaxN],to,wfl,wfr,rt1,rt2;
#define pr(l,r) wfl=l;wfr=r
void add(int l,int r,int u,int &u2)
{
a[u2=++tn]=a[u];
a[u2].c++;
if (l==r)return ;
int mid=(l+r)>>1;
if (to<=mid)add(l,mid,a[u].l,a[u2].l);
else add(mid+1,r,a[u].r,a[u2].r);
}
bool chk(int l=1,int r=n,int u1=rt1,int u2=rt2)
{
if (wfl<=l&&r<=wfr)
return a[u2].c-a[u1].c;
int mid=(l+r)>>1;
return (wfl<=mid&&chk(l,mid,a[u1].l,a[u2].l))||
(mid<wfr&&chk(mid+1,r,a[u1].r,a[u2].r));
}
int qrynxt(int l=1,int r=n,int u1=rt1,int u2=rt2)
{
if (a[u2].c==a[u1].c)return 0;
if (l==r)return tp[l];
int mid=(l+r)>>1;
if (to<=mid&&a[a[u2].l].c-a[a[u1].l].c){
int sav=qrynxt(l,mid,a[u1].l,a[u2].l);
if (sav)return sav;
}return qrynxt(mid+1,r,a[u1].r,a[u2].r);
}
int qrypre(int l=1,int r=n,int u1=rt1,int u2=rt2)
{
if (a[u2].c==a[u1].c)return 0;
if (l==r)return tp[l];
int mid=(l+r)>>1;
if (mid<to&&a[a[u2].r].c-a[a[u1].r].c){
int sav=qrypre(mid+1,r,a[u1].r,a[u2].r);
if (sav)return sav;
}return qrypre(l,mid,a[u1].l,a[u2].l);
}
int main()
{
n=read();int m=read();
for (int i=1,f,t,len;i<n;i++){
f=read();t=read();len=read();
g[f].pb(t);l[f].pb(len);
g[t].pb(f);l[t].pb(len);
}pfs(dep[1]=1);
for (int j=1;j<16;j++)
for (int i=1;i<=n;i++)
f[j][i]=f[j-1][f[j-1][i]];
for (int i=1;i<=n;i++){
to=in[i];
add(1,n,rt[i-1],rt[i]);
}
for (int i=1,u,l,r,las=0;i<=m;i++){
u=read()^las;rt1=rt[(read()^las)-1];rt2=rt[read()^las];
bool fl=0,fm=0,fr=0;
if (in[u]>1){pr(1,in[u]-1);fl=chk();}
pr(in[u],out[u]);fm=chk();
if (out[u]<n){pr(out[u]+1,n);fr=chk();}
if (fm&&(fl||fr))pf("%d\n",las=0);
else if (!(fl||fr)){
to=out[u];int v1=qrypre();
to=in[u];int v2=qrynxt();
pf("%d\n",las=(dis[lca(v1,v2)]-dis[u]));
}else {
to=1;int v1=qrynxt();
to=n;int v2=qrypre();
int v=lca(v1,v2);
if (in[v]<=in[u]&&in[u]<=out[v]){
int ans=2100000000;
if (fl){
to=in[u]-1;v=qrypre();
ans=min(ans,dis[u]-dis[lca(u,v)]);
}if (fr){
to=out[u]+1;v=qrynxt();
ans=min(ans,dis[u]-dis[lca(u,v)]);
}pf("%d\n",las=ans);
}else pf("%d\n",las=(dis[u]+dis[v]-dis[lca(u,v)]*2));
}
}return 0;
}
```