已购买域名 如何做网站,设计狮官网,邯郸网站制作外包,unity 做网站传送门
给出一棵nnn个点的树。接下来给出PPP条树上路径ai→bia_i\to b_iai→bi#xff0c;及其权值cic_ici。最后有QQQ个询问#xff0c;每个询问给出一条树上路径ui→viu_i\to v_iui→vi#xff0c;问在包含ui→viu_i\to v_iui→vi的所有树上路径中#xf…传送门
给出一棵nnn个点的树。接下来给出PPP条树上路径ai→bia_i\to b_iai→bi及其权值cic_ici。最后有QQQ个询问每个询问给出一条树上路径ui→viu_i\to v_iui→vi问在包含ui→viu_i\to v_iui→vi的所有树上路径中包含指ui→viu_i\to v_iui→vi是ai→bia_i\to b_iai→bi的子路径权值第kkk小的路径权值是多少
不妨设dep[u]dep[v]dep[u]dep[v]dep[u]dep[v] 若lca(u,v)ulca(u,v)ulca(u,v)u记ppp是uuu在向vvv方向的儿子 那么包含u→vu\to vu→v的路径a→ba\to ba→b一定满足a∉subtreep,b∈subtreeva\not\in subtree_p,b\in subtree_va∈subtreep,b∈subtreev 若lca(u,v)̸ulca(u,v)\notulca(u,v)u 那么包含u→vu\to vu→v的路径a→ba\to ba→b一定满足a∈subtreeu,b∈subtreeva\in subtree_u,b\in subtree_va∈subtreeu,b∈subtreev
也就是说对于包含u→vu\to vu→v的路径a→ba\to ba→bdfn[a],dfn[b]dfn[a],dfn[b]dfn[a],dfn[b]的取值范围是 一段或两端区间。 因此所有符合条件的路径a→ba\to ba→b可以用二维平面上的 一个或两个矩形 表示出来。
原题要求的就是所有包含询问点的矩形中权值第kkk小的。
考虑整体二分统计一个点在多少个 权值在[l,r][l,r][l,r]内的矩形 中出现过。用扫描线解决。
#includeiostream
#includecstdio
#includealgorithm
using namespace std;
const int N80010;
struct Edge{int v,nxt;}edge[N];
int n,m,q,cnt,head[N];
int fa[N][20],dep[N],ind,dfn[N],lst[N];
int tot,ans[N],sum[N];
struct Rectangle{int xd,xu,yd,yu,v;}rect[N];
bool operator (Rectangle a,Rectangle b){return a.vb.v;}
struct Point{int x,y,k,id;}pt[N],tmp1[N],tmp2[N];
struct Line{int x,yd,yu,v,id;}line[N];
bool operator (Line a,Line b){return a.xb.x?a.idb.id:a.xb.x;}
struct Bit{int val[N];void modify(int l,int r,int v){for(int il;in;i(i(-i))) val[i]v;for(int ir1;in;i(i(-i))) val[i]-v;}int query(int x){int res0;for(;x;x-(x(-x))) resval[x];return res;}
}T;
void add(int u,int v){edge[cnt].vv;edge[cnt].nxthead[u];head[u]cnt;
}
void dfs(int u){dfn[u]ind;for(int i0;fa[u][i];i) fa[u][i1]fa[fa[u][i]][i];for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;if(vfa[u][0]) continue;fa[v][0]u;dep[v]dep[u]1;dfs(v);}lst[u]ind;
}
int jump(int u,int dis){for(int i18;dis;i--){if(dis(1i)){dis-(1i);ufa[u][i];}}return u;
}
int LCA(int u,int v){if(dep[u]dep[v]) swap(u,v);ujump(u,dep[u]-dep[v]);if(uv) return u;for(int i18;i0;i--) if(fa[u][i]!fa[v][i]) ufa[u][i],vfa[v][i];return fa[u][0];
}
void solve(int l,int r,int st,int ed){if(sted) return;if(lr){for(int ist;ied;i) ans[pt[i].id]rect[l].v;return;}int mid(lr)1,siz0;for(int il;imid;i){line[siz](Line){rect[i].xd,rect[i].yd,rect[i].yu,1,0};line[siz](Line){rect[i].xu,rect[i].yd,rect[i].yu,-1,n1};}for(int ist;ied;i) line[siz](Line){pt[i].x,pt[i].y,0,0,i};sort(line1,linesiz1);for(int i1;isiz;i){if(stline[i].idline[i].ided) sum[line[i].id]T.query(line[i].yd);else T.modify(line[i].yd,line[i].yu,line[i].v);}int a0,b0;for(int ist;ied;i){if(sum[i]pt[i].k) tmp1[a]pt[i];else tmp2[b](Point){pt[i].x,pt[i].y,pt[i].k-sum[i],pt[i].id};}for(int ist;ista-1;i) pt[i]tmp1[i-st1];for(int ista;ied;i) pt[i]tmp2[i-st-a1];solve(l,mid,st,sta-1);solve(mid1,r,sta,ed);
}
int main(){scanf(%d%d%d,n,m,q);for(int i1;in;i){int a,b;scanf(%d%d,a,b);add(a,b);add(b,a);}dfs(1);for(int i1;im;i){int a,b,c;scanf(%d%d%d,a,b,c);int uLCA(a,b);if(dfn[a]dfn[b]) swap(a,b);if(u!a) rect[tot](Rectangle){dfn[a],lst[a],dfn[b],lst[b],c};else{int wjump(b,dep[b]-dep[a]-1);rect[tot](Rectangle){1,dfn[w]-1,dfn[b],lst[b],c};if(lst[w]n) rect[tot](Rectangle){dfn[b],lst[b],lst[w]1,n,c};}}sort(rect1,recttot1);for(int i1;iq;i){int a,b,k;scanf(%d%d%d,a,b,k);if(dfn[a]dfn[b]) swap(a,b);pt[i](Point){dfn[a],dfn[b],k,i};}solve(1,tot,1,q);for(int i1;iq;i) printf(%d\n,ans[i]);return 0;
}
