其实题目也没问题，大概是我自己的问题吧。。。我把ancestor理解为了parent，也就是直接的父节点，而不是到根节点路径上的点。。。

题目链接：http://codeforces.com/contest/932/problem/D

题意：你有一颗树，以1为根节点，且1号点权值为0，接下来有Q(Q<=400000)次操作，1 R W新建节点，编号为cnt+1，与R相连，权值为W，2 R X查询从R开始的最长路径长度，设路径上点为a[1],a[2]...a[m]，满足a[i]是a[i-1]的祖先（ancestor），且a[i]的权值大于等于a[i-1]，且路径上点的权值和小于等于X。在线。

题解：显然每次加入点不会影响之前的点，然后这个问题显然很“倍增”，f[i][j]不再是i的2^j祖先，而是i的2^j满足权值大于等于i的祖先，g[i][j]是权值和没有问题，考虑怎么得出f[i][j],我们要找i到根节点上离i最近的权值大于等于i的点，那么我们在R的f中二分就行了，查询也是二分，把sum算出来与X比较即可。

#include
      
       typedef long long LL;const int N=400010;LL q,lst,n,f[N][20],g[N][20],a[N],dep[N];int getfa(LL x,LL y){    for (int i=19;i>=0;i--)        if (y>=(1<
       
        =0;i--)        if (y>=(1<
        
         >1;                if (a[getfa(R,mid)]>=a[n]) ans=mid,r=mid-1; else l=mid+1;            }            f[n][0]=getfa(R,ans); g[n][0]=W;            if (a[getfa(R,ans)]
         
          >1;                if (check(R,mid,W)) ans=mid,l=mid+1; else r=mid-1;            }            printf("%d\n",ans);            lst=ans;        }    }    return 0;}