bzoj4009 [HNOI2015]接水果

  1 #include<bits/stdc++.h>
  2 #define rep(i,x,y) for (int i=(x);i<=(y);i++)
  3 #define per(i,x,y) for (int i=(x);i>=(y);i--)
  4 #define ll long long
  5 #define inf 1000000001
  6 #define y1 y1___
  7 using namespace std;
  8 char gc(){
  9     static char buf[100000],*p1=buf,*p2=buf;
 10     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
 11 }
 12 #define gc getchar
 13 ll read(){
 14     char ch=gc();ll x=0;int op=1;
 15     for (;!isdigit(ch);ch=gc()) if (ch==‘-‘) op=-1;
 16     for (;isdigit(ch);ch=gc()) x=(x<<1)+(x<<3)+ch-‘0‘;
 17     return x*op;
 18 }
 19 #define N 100005
 20 int n,m,Q,cnt,head[N],f[N][20],dep[N],in[N],out[N],clk,ans[N],sum[N],ma_tot;
 21 struct edge{int to,nxt;}e[N<<1];
 22 void adde(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
 23 struct matrix{
 24     int x1,y1,x2,y2,w;
 25     matrix(){}
 26     matrix(int x1_,int y1_,int x2_,int y2_,int w_){x1=x1_,y1=y1_,x2=x2_,y2=y2_,w=w_;}
 27 }ma[N<<1];
 28 bool cmp_m(matrix x,matrix y){return x.w<y.w;}
 29 struct point{
 30     int x,y,k,id;
 31     point(){}
 32     point(int x_,int y_,int k_,int id_){x=x_,y=y_,k=k_,id=id_;}
 33 }po[N],nq[N];
 34 struct event{
 35     int x,y1,y2,w,id;
 36     event(){}
 37     event(int x_,int y1_,int y2_,int w_,int id_){x=x_,y1=y1_,y2=y2_,w=w_,id=id_;}
 38 }q[N];
 39 bool cmp_q(event x,event y){return x.x<y.x||x.x==y.x&&x.id<y.id;}
 40 void dfs(int u){
 41     in[u]=++clk;
 42     rep (i,1,16) f[u][i]=f[f[u][i-1]][i-1];
 43     for (int i=head[u];i;i=e[i].nxt){
 44         int v=e[i].to;if (v==f[u][0]) continue;
 45         f[v][0]=u;dep[v]=dep[u]+1;
 46         dfs(v);
 47     }
 48     out[u]=clk;
 49 }
 50 bool isanc(int x,int y){return in[x]<=in[y]&&out[y]<=out[x];}
 51 int jump(int x,int y){
 52     int tmp=dep[x]-dep[y]-1;
 53     per (i,16,0) if (tmp>>i&1) x=f[x][i];return x;
 54 }
 55 int bit[N];
 56 void add(int x,int y){for (int i=x;i<=n;i+=i&-i) bit[i]+=y;}
 57 int qry(int x){int s=0;for (int i=x;i;i-=i&-i) s+=bit[i];return s;}
 58 void solve(int l,int r,int L,int R){
 59     if (L>R) return;
 60     if (l==r){
 61         rep (i,L,R) ans[po[i].id]=ma[l].w;
 62         return;
 63     }
 64     int mid=l+r>>1,top=0;
 65     //统计一个点被多少个矩形覆盖：扫描线+树状数组
 66     rep (i,l,mid){
 67         q[++top]=event(ma[i].x1,ma[i].y1,ma[i].y2,1,0);
 68         q[++top]=event(ma[i].x2,ma[i].y1,ma[i].y2,-1,Q+1);
 69     }
 70     rep (i,L,R) q[++top]=event(po[i].x,po[i].y,0,0,i);
 71     sort(&q[1],&q[top+1],cmp_q);
 72     rep (i,1,top)
 73         if (q[i].w==0) sum[q[i].id]=qry(q[i].y1);
 74         else add(q[i].y1,q[i].w),add(q[i].y2+1,-q[i].w);
 75     int l1=L-1,r1=R+1;
 76     rep (i,L,R)
 77         if (sum[i]>=po[i].k) nq[++l1]=po[i];else nq[--r1]=po[i],nq[r1].k-=sum[i];
 78     rep (i,L,R) po[i]=nq[i];
 79     solve(l,mid,L,l1);solve(mid+1,r,r1,R);
 80 }
 81 int main(){
 82     n=read(),m=read(),Q=read();
 83     rep (i,1,n-1){int x=read(),y=read();adde(x,y);adde(y,x);}
 84     dfs(1);
 85     rep (i,1,m){
 86         int x=read(),y=read(),w=read();
 87         if (in[x]>in[y]) swap(x,y);
 88         if (!isanc(x,y)) ma[++ma_tot]=matrix(in[x],in[y],out[x],out[y],w);
 89         else{
 90             x=jump(y,x);
 91             ma[++ma_tot]=matrix(1,in[y],in[x]-1,out[y],w);
 92             if (out[x]+1<=n) ma[++ma_tot]=matrix(in[y],out[x]+1,out[y],n,w);//注意这里由于要保证x<y，所以要交换矩形的x,y坐标
 93         }
 94     }
 95     sort(&ma[1],&ma[ma_tot+1],cmp_m);
 96     rep (i,1,Q){
 97         int x=read(),y=read(),w=read();
 98         if (in[x]>in[y]) swap(x,y);
 99         po[i]=point(in[x],in[y],w,i);
100     }
101     solve(1,ma_tot,1,Q);
102     rep (i,1,Q) printf("%d\n",ans[i]);
103     return 0;
104 }