将树上的路径包含问题通过dfs序转换为双关键字区间包含问题，

进而转换为区间覆盖类问题。

　　由此，我们可以通过二分得出每一个询问的答案。

　　由于有多次询问，故只需要整体二分即可。

 

1 #include
      
         2 using namespace std;  3 int n,p,q,x,y,z;  4 int head[100050],tot;  5 int nex[100050];  6 int ver[100050];  7 int siz[100050];  8 int ans[100050];  9 int pos[200050]; 10 int tl[100050]; 11 int tr[100050]; 12 int w[100050]; 13 int t[100050],top; 14 int bz[100050][20]; 15 int f[200050],sf; 16 int g[200050],sg; 17 int c[100050]; 18 void calc_add(int u,int v) 19 { 20     t[++top]=u; 21     while(u<=n) 22     { 23         c[u]+=v; 24         u+=u&-u; 25     } 26 } 27 int calc_ask(int u) 28 { 29     int sum=0; 30     while(u) 31     { 32         sum+=c[u]; 33         u-=u&-u;  34     } 35     return sum; 36 } 37 void calc_clear() 38 { 39     while(top) 40     { 41         while(t[top]<=n) 42         { 43             c[t[top]]=0; 44             t[top]+=t[top]&-t[top]; 45         } 46         --top; 47     } 48 } 49 struct node 50 { 51     int opt,x,y,l,r,val; 52     bool operator<(const node &p )const 53     { 54         return x==p.x? opt
       
        
         0) 83                 ans[num[pos[i]].opt]=w[L]; 84         return ; 85     } 86     int sf=0,sg=0; 87     bool flagf=0; 88     bool flagg=0; 89     int mid=(L+R)>>1; 90     for(int i=l,j;i<=r;++i) 91     { 92         j=pos[i]; 93         if(num[j].opt<0) 94         { 95             if(num[j].val<=mid) 96             { 97                 calc_add(num[j].l,num[j].opt+2); 98                 calc_add(num[j].r+1,-(num[j].opt+2)); 99                 f[++sf]=j;100             }101             else102                 g[++sg]=j;103         }104         else105         {106             int tmp=calc_ask(num[j].y);107             if(tmp>=num[j].val)108             {109                 f[++sf]=j;110                 flagf=true;111             }112             else113             {114                 g[++sg]=j;115                 flagg=true;116                 num[j].val-=tmp;117             }118         }119     }120     calc_clear();121     for(int i=1;i<=sf;++i)    pos[l-1+i]=f[i];122     for(int i=1;i<=sg;++i)    pos[l-1+sf+i]=g[i];123     if(flagf)    solve(l,l-1+sf,L,mid);124     if(flagg)    solve(l-1+sf+1,r,mid+1,R);125 }126 void ad(int opt,int x,int l,int r)127 {128     if(l>r)    return ;129     ++tot;130     num[tot].opt=opt;131     num[tot].x=x;132     num[tot].l=l;133     num[tot].r=r;134     num[tot].val=z;135 }136 int main()137 {138     scanf("%d%d%d",&n,&p,&q);139     for(int i=1;i
         
          tl[y])    swap(x,y);150         if(tl[x]<=tl[y]&&tr[x]>=tl[y])151         {152             int tmp=y;153             for(int k=18;k>=0;--k)154                 if(tl[bz[tmp][k]]>tl[x])155                     tmp=bz[tmp][k];156             ad(-1,1,tl[y],tr[y]);157             ad(-3,tl[tmp]-1+1,tl[y],tr[y]);158             ad(-1,tl[y],tr[tmp]+1,n);159             ad(-3,tr[y]+1,tr[tmp]+1,n);160         }161         else162         {163             ad(-1,tl[x],tl[y],tr[y]);164             ad(-3,tr[x]+1,tl[y],tr[y]);165         }166     }167     sort(t+1,t+top+1);168     top=unique(t+1,t+top+1)-t-1;169     for(int i=1;i<=top;++i)    w[i]=t[i];170     int tp=top; top=0;171     for(int i=1;i<=tot;++i)    num[i].val=lower_bound(t+1,t+tp+1,num[i].val)-t;172     for(int i=1;i<=q;++i)173     {174         ++tot;    num[tot].opt=i;175         scanf("%d%d%d",&num[tot].x,&num[tot].y,&num[tot].val);176         if(tl[num[tot].x]>tl[num[tot].y])    swap(num[tot].x,num[tot].y);177         num[tot].x=tl[num[tot].x];    num[tot].y=tl[num[tot].y];178     }179     sort(num+1,num+tot+1);180     for(int i=1;i<=tot;++i)    pos[i]=i;181     solve(1,tot,1,tp);182     for(int i=1;i<=q;++i)183         printf("%d\n",ans[i]);184     return 0;185 }