为什么这一道题被权限了啊 好气啊
题意就是，先给你若干条链，然后每次给你一条链问之前给的那些链里面是它子链的权值第\(k\)小的是多少。
可以想到，如果一条链是另一条的子链，那么可以按是否有一个点是另一个点父亲分两种情况。
那么我们写出对父链的约束条件，可以发现是一个类似矩阵的东西。
即把问题转化为：先给你若干个矩阵，每次问你覆盖某个点的矩阵中权值第\(k\)小的是多少。
于是用整体二分。计算点在多少矩阵内用扫描线+树状数组。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
// <4009.cpp> - Tue Feb 21 17:55:16 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; #define next nxt #define end edn template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=40010; const int MAXM=80010; const int K=17; const int INF=1e9; int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM]; inline void add(int x,int y,int z=0){ next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z; next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z; } int dt,dfn[MAXN],end[MAXN],f[K][MAXN],dep[MAXN]; void dfs(int x){ dfn[x]=++dt; for(int i=b[x];i;i=next[i]){ if(to[i]==f[0][x])continue; f[0][to[i]]=x; dep[to[i]]=dep[x]+1; dfs(to[i]); } end[x]=dt; } int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); int d=dep[x]-dep[y]; for(int i=0,p=1;i<K;i++,p<<=1) if(d&p)x=f[i][x]; if(x==y)return x; for(int i=K-1;i>=0;i--){ if(f[i][x]==f[i][y])continue; x=f[i][x];y=f[i][y]; } return f[0][x]; } struct matrix{ int lx,rx,ly,ry,v; bool operator <(const matrix b) const{return v<b.v;} }t[MAXM]; struct query{ int x,y,k,id; bool operator <(const query b) const{return x<b.x;} }q[MAXN],ql[MAXN],qr[MAXN]; struct eve{ int t,p,x; bool operator <(const eve b) const{return t<b.t;} }e[MAXN<<3]; int n,c[MAXN]; inline void mod(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;} inline int get(int x){ int res=0; for(;x;x-=x&-x)res+=c[x]; return res; } int ans[MAXN]; void work(int L,int R,int l,int r){ if(L>R)return; if(l==r){ for(int i=L;i<=R;i++)ans[q[i].id]=t[l].v; return; } int m=l+r>>1,et=0; for(int i=l;i<=m;i++){ e[++et]=(eve){t[i].lx,t[i].ly,1}; e[++et]=(eve){t[i].lx,t[i].ry+1,-1}; e[++et]=(eve){t[i].rx+1,t[i].ly,-1}; e[++et]=(eve){t[i].rx+1,t[i].ry+1,1}; } sort(e+1,e+et+1); int p=1,lt=0,rt=0; for(int i=L;i<=R;i++){ for(;p<=et&&e[p].t<=q[i].x;p++)mod(e[p].p,e[p].x); int nk=get(q[i].y); if(q[i].k<=nk)ql[lt++]=q[i]; else{q[i].k-=nk;qr[rt++]=q[i];} } for(;p<=et;p++)mod(e[p].p,e[p].x); for(int i=0;i<lt;i++)q[L+i]=ql[i]; for(int i=0;i<rt;i++)q[L+lt+i]=qr[i]; work(L,L+lt-1,l,m); work(L+lt,R,m+1,r); } int main(){ n=gi();int P=gi(),Q=gi(); for(int i=1;i<n;i++)add(gi(),gi()); dfs(1); for(int j=1;j<K;j++) for(int i=1;i<=n;i++)f[j][i]=f[j-1][f[j-1][i]]; int mt=0; for(int i=1;i<=P;i++){ int x=gi(),y=gi(),z=gi(),L=lca(x,y); if(dfn[x]>dfn[y])swap(x,y); if(L==x){ int d=dep[y]-dep[x]-1,w=y; for(int i=0,p=1;i<K;i++,p<<=1)if(d&p)w=f[i][w]; t[++mt]=(matrix){1,dfn[w]-1,dfn[y],end[y],z}; t[++mt]=(matrix){dfn[y],end[y],end[w]+1,n,z}; }else t[++mt]=(matrix){dfn[x],end[x],dfn[y],end[y],z}; } sort(t+1,t+mt+1); for(int i=1;i<=Q;i++){ q[i].x=dfn[gi()],q[i].y=dfn[gi()],q[i].k=gi(),q[i].id=i; if(q[i].x>q[i].y)swap(q[i].x,q[i].y); } sort(q+1,q+Q+1); work(1,Q,1,mt); for(int i=1;i<=Q;i++)printf("%d\n",ans[i]); return 0; } |
说点什么