本文共 1253 字，大约阅读时间需要 4 分钟。
n<=400000个在线操作：树上插入一个某点权、父亲为某点的点；查询这样的最长点序列：序列的某个数必须是上一个数的祖先之一；序列的点权和不能超过x；序列的某个点的点权必须不小于上一个，且相邻两个点之间不存在点权大于等于深度大的那个点的点权的点。
说白了，就是每个点找他祖先中第一个点权大于等于他的点，然后建一棵假的树，树边表示某点如果要构造序列，序列的下一个数字就是他祖先。
分别处理：原树父亲、祖先点权最大值、假的树的父亲、假的树的祖先点权和，四个st表一个推一个即可。
1 //#include 2 #include 3 #include 4 #include 5 //#include 6 #include 7 //#include 8 //#include 9 #include 10 using namespace std;11 12 int n;13 #define maxn 40001114 #define LL long long15 LL fa[maxn][22],val[maxn],M[maxn][22],pp[maxn][22],sum[maxn][22],tot=1;16 17 int main()18 {19 scanf("%d",&n);20 int last=0; LL x,y,z;21 for (int i=1;i<=n;i++)22 {23 scanf("%lld%lld%lld",&x,&y,&z); y^=last; z^=last;24 if (x==1)25 {26 val[++tot]=z;27 fa[tot][0]=y; for (int i=1;i<=20;i++) fa[tot][i]=fa[fa[tot][i-1]][i-1];28 M[tot][0]=max(val[y],z); for (int i=1;i<=20;i++) M[tot][i]=max(M[tot][i-1],M[fa[tot][i-1]][i-1]);29 if (val[y]>=z) pp[tot][0]=y;30 else31 {32 int t=y; for (int i=20;i>=0;i--) if (fa[t][i] && M[t][i] z) {printf("%d\n",(last=0)); continue;}42 int t=y,ans=1; for (int i=20;i>=0;i--) if (pp[t][i] && sum[t][i]<=z) ans+=(1<
转载于:https://www.cnblogs.com/Blue233333/p/8485929.html
