Codeforces932D. Tree

n<=400000个在线操作：树上插入一个某点权、父亲为某点的点；查询这样的最长点序列：序列的某个数必须是上一个数的祖先之一；序列的点权和不能超过x；序列的某个点的点权必须不小于上一个，且相邻两个点之间不存在点权大于等于深度大的那个点的点权的点。

说白了，就是每个点找他祖先中第一个点权大于等于他的点，然后建一棵假的树，树边表示某点如果要构造序列，序列的下一个数字就是他祖先。

分别处理：原树父亲、祖先点权最大值、假的树的父亲、假的树的祖先点权和，四个st表一个推一个即可。

 //#include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 //#include<map>

 #include<math.h>

 //#include<time.h>

 //#include<complex>

 #include<algorithm>

 using namespace std;

 int n;

 #define maxn 400011

 #define LL long long

 LL fa[maxn][],val[maxn],M[maxn][],pp[maxn][],sum[maxn][],tot=;

 int main()

 {

     scanf("%d",&n);

     int last=; LL x,y,z;

     for (int i=;i<=n;i++)

     {

         scanf("%lld%lld%lld",&x,&y,&z); y^=last; z^=last;

         if (x==)

         {

             val[++tot]=z;

             fa[tot][]=y; for (int i=;i<=;i++) fa[tot][i]=fa[fa[tot][i-]][i-];

             M[tot][]=max(val[y],z); for (int i=;i<=;i++) M[tot][i]=max(M[tot][i-],M[fa[tot][i-]][i-]);

             if (val[y]>=z) pp[tot][]=y;

             else

             {

                 int t=y; for (int i=;i>=;i--) if (fa[t][i] && M[t][i]<z) t=fa[t][i]; t=fa[t][];

                 pp[tot][]=t;

             }

             for (int i=;i<=;i++) pp[tot][i]=pp[pp[tot][i-]][i-];

             sum[tot][]=val[tot]+val[pp[tot][]];

             for (int i=;i<=;i++) sum[tot][i]=sum[tot][i-]+sum[pp[tot][i-]][i-]-val[pp[tot][i-]];

         }

         else

         {

             if (val[y]>z) {printf("%d\n",(last=)); continue;}

             int t=y,ans=; for (int i=;i>=;i--) if (pp[t][i] && sum[t][i]<=z) ans+=(<<i),z-=sum[t][i]-val[pp[t][i]],t=pp[t][i];

             printf("%d\n",(last=ans));

         }

     }

     return ;

 }

巴特西

Codeforces932D. Tree

最新文章

热门文章