[loj#2113] [HNOI2015] 接水果
题意简述
给定 (n) 个节点的树。
给定 (P) 个盘子，每个盘子是树上一条从 (u) 到 (v) 的路径，有权值 (c)
给定 (Q) 个水果，每个水果是树上一条从 (u) 到 (v) 的路径。
一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径。
对每个水果，求可接住它的盘子中第 (k_i) 小的权值。
(n,P,Q leq 40000)
想法
重点在于如何判断一条路径是否为另一条路径的子路径。
假设我们要找包含路径 (u) 到 (v) 的路径（即路径 (u) 到 (v) 是哪些路径的子路径）。
假设 (u) 的 (dfs) 序更小，设 (u) 与 (v) 的 (lca) 为 (L)
有两种情况：
1.(L
eq u) 且 (L
eq v)，即这条路径有拐弯
易知包含它的路径一端在 (u) 子树中，一端在 (v) 子树中
2.(L=u)
设 (z) 为这条路径上 (u) 下面的第一个点。则包含这条路径的路径一端在 (v) 子树中，另一端在 非(z)子树 的那些点中（画图可发现）
把每条路径投射到二维平面上的点 ((u,v))，(u,v) 为路径的两端点且(u) 的 (dfs) 序更小
发现上面两种情况对应的路径是二维平面上的一些矩形。
再回来考虑第 (k) 大，显然可以二分答案，然后扫描线+树状数组判断。
有多组询问，用整体二分。
总结
思想
1.树上路径投射成二维平面上的点 ((u,v))
2.扫描线不一定配线段树，树状数组常数更小。
码力
此处应划重点！！
1.数组大小！！！！！！！！！！特别注意不要以为有的注意了就说明所有都注意了，所以都还要好好检查！！！！！！
2.(a!=b.a?a<b.a:c>b.c) 这个判断一定要写清楚……别写反了……
3.整体二分中全局变量与局部变量的问题！！比如 (cnt1,cnt2) 应设为内部的变量，不然递归一般后大小变了
4.这个题差分比较多，想清楚。。
5.树状数组！我咋能忘了咋用呢。。。此题中是区间修改、单点查询，所以查询时不用减前面的了……写之前要搞清楚
6.别忘了离散化哦
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
const int N = 40005;
int n,pla,fru;
struct node{
int v;
node *nxt;
}pool[N*2],*h[N];
int cnt;
void addedge(int u,int v){
node *p=&pool[++cnt],*q=&pool[++cnt];
p->v=v;p->nxt=h[u];h[u]=p;
q->v=u;q->nxt=h[v];h[v]=q;
}
int dfn[N],dep[N],fa[N][18],out[N],tot;
void dfs(int u){
int v;
dfn[u]=++tot;
for(node *p=h[u];p;p=p->nxt)
if(!dfn[v=p->v]) {
fa[v][0]=u; dep[v]=dep[u]+1;
for(int j=1;j<16;j++) fa[v][j]=fa[fa[v][j-1]][j-1];
dfs(v);
}
out[u]=tot;
}
int fst(int u,int v){
for(int i=15;i>=0;i--) if(dep[fa[v][i]]>dep[u]) v=fa[v][i];
return v;
}
int mmp[N];
map<int,int> mp;
struct data{
int a,l,r,c,k,id; //c==-1?fruit:plate
bool operator < (const data &b) const{
return a!=b.a?a<b.a:c>b.c;
}
}d[N*6],t1[N*6],t2[N*6]; /*all N*6*/
int num;
int C[N];
void add(int x,int y) { while(x<=n) C[x]+=y,x+=x&(-x); }
int sum(int x) { int ret=0; while(x) ret+=C[x],x-=x&(-x); return ret; }
int ans[N];
void work(int l,int r,int L,int R){
if(L>R || l>r) return;
if(l==r){
for(int i=L;i<=R;i++) if(d[i].c==-1) ans[d[i].id]=l;
return;
}
int flag=0;
for(int i=L;i<=R;i++) if(d[i].c==-1) flag=1;
if(!flag) return;
int mid=(l+r)>>1,s;
int cnt1=0,cnt2=0; //inner
for(int i=L;i<=R;i++){
if(d[i].c==-1){
s=sum(d[i].l); /*dandian query*/
if(s<d[i].k) d[i].k-=s,t2[++cnt2]=d[i];
else t1[++cnt1]=d[i];
}
else{
if(d[i].c>mid) t2[++cnt2]=d[i];
else {
t1[++cnt1]=d[i];
add(d[i].l,d[i].k); add(d[i].r+1,-d[i].k); /*r+1*/
}
}
}
for(int i=1;i<=cnt1;i++)
if(t1[i].c!=-1) {
add(t1[i].l,-t1[i].k);
add(t1[i].r+1,t1[i].k); /*r+1*/
}
for(int i=1;i<=cnt1;i++) d[L+i-1]=t1[i];
for(int i=1;i<=cnt2;i++) d[L+cnt1+i-1]=t2[i];
work(l,mid,L,L+cnt1-1); work(mid+1,r,L+cnt1,R);
}
int main()
{
n=read(); pla=read(); fru=read();
for(int i=1;i<n;i++) addedge(read(),read());
dep[1]=1; dfs(1);
int mx=0,u,v,z,c;
for(int i=1;i<=pla;i++){
u=read(); v=read(); c=read(); mmp[i]=c;
if(dfn[u]>dfn[v]) swap(u,v);
if(dfn[v]<=out[u]) {//u->v:(1,dfn[v])-(dfn[z]-1,out[v]);(dfn[v],out[z]+1)-(out[v],n)
z=fst(u,v);
if(dfn[z]-1>0){
++num; d[num].a=1; d[num].l=dfn[v]; d[num].r=out[v]; d[num].c=c; d[num].k=1;
++num; d[num].a=dfn[z]; d[num].l=dfn[v]; d[num].r=out[v]; d[num].c=c; d[num].k=-1;
}
if(out[z]+1<=n){
++num; d[num].a=dfn[v]; d[num].l=out[z]+1; d[num].r=n; d[num].c=c; d[num].k=1;
++num; d[num].a=out[v]+1; d[num].l=out[z]+1; d[num].r=n; d[num].c=c; d[num].k=-1;
}
}
else{ //(dfn[u],dfn[v])-(out[u],out[v])
++num; d[num].a=dfn[u]; d[num].l=dfn[v]; d[num].r=out[v]; d[num].c=c; d[num].k=1;
++num; d[num].a=out[u]+1; d[num].l=dfn[v]; d[num].r=out[v]; d[num].c=c; d[num].k=-1;
}
}
for(int i=1+num;i<=fru+num;i++){
u=read(); v=read(); if(dfn[u]>dfn[v]) swap(u,v);
d[i].a=dfn[u]; d[i].l=d[i].r=dfn[v]; d[i].c=-1; d[i].k=read(); d[i].id=i-num; /*dfn*/
}
num+=fru;
sort(mmp+1,mmp+1+pla);
mx=unique(mmp+1,mmp+1+pla)-mmp-1;
for(int i=1;i<=mx;i++) mp[mmp[i]]=i;
for(int i=1;i<=num;i++)
if(d[i].c!=-1) d[i].c=mp[d[i].c];
sort(d+1,d+1+num);
work(1,mx,1,num);
for(int i=1;i<=fru;i++) printf("%d
",mmp[ans[i]]);
return 0;
}