【题解】

　　每个情报员的危险值val[i]应该是一个分段函数，前面一段是平行于x轴的横线，后面一段是一次函数。我们可以用fx(t)=t-b[x]表示这个一次函数。每次询问一条链上fx(t)大于c的点的个数，也就是问有多少个点满足t-b[x]>c，移项得b[x]<t-c，不等式左边只与点有关，可以当做点权，右边只与询问有关。因此我们可以写没有修改的主席树。

　　同时这道题也可以离线后用树状数组写。我们维护某个点到根的链上小于等于某个值的数的个数Cnt，这开一个权值树状数组就可以做到。这样每个询问(x,y)的答案就是Cnt[x]+Cnt[y]-Cnt[lca]-Cnt[fa[lca]]. 我们dfs进行维护，进入这个点的时候在树状数组中加入点权，退出这个点的时候删除点权，同时在每个点计算与这个点有关的答案即可。

　　

1 #include
      
        2 #include
       
         3 #include
        
          4 #define N 200010 5 #define rg register 6 using namespace std; 7 int n,m,rt,tot,cnt,ret,last[N],ans[N],ans2[N],fa[N],hvy[N],size[N],top[N],dep[N],t[N],val[N]; 8 vector
         
          son[N]; 9 struct rec{10     int pos,val,type,pre;11 }data[N<<2];12 inline int read(){13     int k=0,f=1; char c=getchar();14     while(c<'0'||c>'9')c=getchar();15     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();16     return k*f;17 }18 void dfs1(int x){19     size[x]=1; dep[x]=dep[fa[x]]+1;20     for(rg int i=0,s;i
          
           size[hvy[x]]) hvy[x]=s;23     }24 }25 void dfs2(int x,int tp){26     top[x]=tp;27     if(hvy[x]) dfs2(hvy[x],tp);28     for(rg int i=0,s;i
           
            0;j-=(j&-j)) ret+=t[j];44 ans[data[i].pos]+=data[i].type*ret;45 }46 for(rg int i=0;i