(题目链接)

题意

　　给出一颗无根树。有一些路径记为$P_i$，这些路径有两个端点和一个权值$W_i$。另外一些路径记为$Q_i$，同样有两个端点和一个权值$K_i$。对于每个$Q_i$，询问$P$中路径是它的路径的子集的第$K_i$大的权值。

Solution

　　整体二分很明显。怎么维护信息呢。右转题解：

　　所以线段树扫描线一搞就可以了。

细节

　　不知不觉4KB了，可啪

代码

// bzoj4009#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define LL long long#define inf (1ll<<30)#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=40010;int deep[maxn],in[maxn],out[maxn],head[maxn],fa[maxn][30],bin[30];int vis[maxn],ans[maxn],sum[maxn],a[maxn];int n,m,P,Q,dfn,cnt;struct edge {int to,next;}e[maxn<<1];struct node {int l,r,s,tag;}tr[maxn<<2];struct event {int x,l,r,w,id,op;}p[maxn<<2],q[maxn],ql[maxn],qr[maxn];namespace Segtree { void build(int k,int s,int t) { tr[k].l=s,tr[k].r=t; if (s==t) return; int mid=(s+t)>>1; build(k<<1,s,mid);build(k<<1|1,mid+1,t); } void pushdown(int k) { tr[k<<1].s+=tr[k].tag;tr[k<<1|1].s+=tr[k].tag; tr[k<<1].tag+=tr[k].tag;tr[k<<1|1].tag+=tr[k].tag; tr[k].tag=0; } void add(int k,int s,int t,int val) { int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1; if (s==l && t==r) {tr[k].s+=val,tr[k].tag+=val;return;} if (tr[k].tag) pushdown(k); if (t<=mid) add(k<<1,s,t,val); else if (s>mid) add(k<<1|1,s,t,val); else add(k<<1,s,mid,val),add(k<<1|1,mid+1,t,val); tr[k].s=tr[k<<1].s+tr[k<<1|1].s; } int query(int k,int s,int t) { int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1; if (s==l && t==r) return tr[k].s; if (tr[k].tag) pushdown(k); if (t<=mid) return query(k<<1,s,t); else if (s>mid) return query(k<<1|1,s,t); else return query(k<<1,s,mid)+query(k<<1|1,mid+1,t); }}using namespace Segtree;namespace Prepare { bool cmpw(event a,event b) {return a.w
           
            =0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return x==y ? x : fa[x][0]; }}using namespace Prepare;void solve(int al,int ar,int pl,int pr,int L,int R) { if (pl>pr || L>R) return; if (al==ar) { for (int i=L;i<=R;i++) ans[q[i].id]=al; return; } sort(p+pl,p+pr+1,cmpw); int mid=(al+ar)>>1; int x=pl,y=L,cl=0,cr=0,lim; for (lim=pl;p[lim].w<=mid;lim++);lim--; sort(p+pl,p+lim+1,cmpx); while (x<=lim || y<=R) { if (y>R || (x<=lim && cmpx(p[x],q[y]))) add(1,p[x].l,p[x].r,p[x].id),x++; else { a[q[y].id]=query(1,q[y].l,q[y].r); if (q[y].w<=sum[q[y].id]+a[q[y].id]) ql[++cl]=q[y]; else qr[++cr]=q[y]; y++; } } for (int i=1;i<=cl;i++) q[L+i-1]=ql[i]; for (int i=cr;i>=1;i--) q[R-cr+i]=qr[i]; solve(al,mid,pl,lim,L,cl+L-1); for (int i=L;i<=R;i++) sum[q[i].id]+=a[q[i].id]; solve(mid+1,ar,lim+1,pr,R-cr+1,R);}int main() { bin[0]=1;for (int i=1;i<=20;i++) bin[i]=bin[i-1]<<1; scanf("%d%d%d",&n,&P,&Q); for (int u,v,i=1;i
            
             in[v]) swap(u,v); int f=lca(u,v); if (f!=u) { p[++m]=(event){in[u],in[v],out[v],w,1,1}; p[++m]=(event){out[u],in[v],out[v],w,-1,3}; } else { int d=deep[v]-deep[u]-1;u=v; for (int i=0;bin[i]<=d;i++) if (bin[i]&d) u=fa[u][i]; p[++m]=(event){1,in[v],out[v],w,1,1}; p[++m]=(event){in[u]-1,in[v],out[v],w,-1,3}; if (out[u]
             
              in[v]) swap(u,v); q[i]=(event){in[u],in[v],in[v],w,i,2}; } sort(q+1,q+1+Q,cmpx); build(1,1,n); solve(mn,mx,1,m,1,Q); for (int i=1;i<=Q;i++) printf("%d\n",ans[i]); return 0;}