网站制作小常识,中国住房和城乡建设网,做搜狗pc网站软件下载,wordpress推介传送门
题意#xff1a;给定一个nnn个点的树#xff0c;定义一个“盘子”为一个给定权值的路径#xff0c;一个“水果”为一条路径#xff0c;一个盘子可以接到水果当且仅当盘子的路径是水果的子路径。给出所有盘子和水果#xff0c;对于每个水果求可以接它的盘子中第kik…传送门
题意给定一个nnn个点的树定义一个“盘子”为一个给定权值的路径一个“水果”为一条路径一个盘子可以接到水果当且仅当盘子的路径是水果的子路径。给出所有盘子和水果对于每个水果求可以接它的盘子中第kik_iki小的权值。
n≤4×105n\leq 4\times10^5n≤4×105
显然这种奇奇怪怪的第kkk小考虑整体二分
给盘子按权值排序对于一个盘子和水果的区间要计算出每个水果可以被区间内多少个盘子接住。
根据惯用套路把一条路径抽象成按 DFS 为坐标的点一个盘子可以接的是一个或两个矩形中的水果。
无脑扫描线即可。因为是区间修改单点查询可以差分后树状数组。
复杂度O(能过)O(能过)O(能过)
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#define MAXN 100005
#define MAXM 200005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
struct edge{int u,v;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
void addnode(int u,int v)
{e[cnt](edge){u,v};nxt[cnt]head[u];head[u]cnt;
}
int dfn[MAXN],ed[MAXN],dep[MAXN],fa[MAXN][16],tim;
void dfs(int u)
{for (int i1;i16;i) fa[u][i]fa[fa[u][i-1]][i-1];dfn[u]tim;for (int ihead[u];i;inxt[i])if (!dfn[e[i].v])dep[e[i].v]dep[u]1,fa[e[i].v][0]u,dfs(e[i].v);ed[u]tim;
}
int n,p,q;
int ans[MAXN];
struct Pan{int a,b,c;}pan[MAXN];
struct fruit{int u,v,k,id;}fru[MAXN],L[MAXN],R[MAXN];
inline bool operator (const Pan x,const Pan y){return x.cy.c;}
struct node{int type,x,l,r,id;}lis[MAXM];
//trangle: -1,x,yl,yr
//point: 0,x,y,k
inline bool operator (const node a,const node b)
{if (a.xb.x) return (unsigned)a.type(unsigned)b.type;return a.xb.x;
}
struct BIT
{int s[MAXN];inline int lowbit(const int x){return x-x;}inline void modify(int x,int v){for (;xn;s[x]v,xlowbit(x));}inline int query(int x,int ans0){for (;x;anss[x],x-lowbit(x));return ans;}
}bit;
void solve(int l,int r,int vl,int vr)
{if (lr||vlvr) return;if (vlvr){for (int il;ir;i) ans[fru[i].id]pan[vl].c;return;}int vmid(vlvr)1;int tot0;for (int ivl;ivmid;i){int upan[i].a,vpan[i].b;if (dfn[v]ed[u]){int tdep[v]-dep[u]-1;uv;for (int i0;(1i)t;i) if (t(1i)) ufa[u][i];lis[tot](node){1,1,dfn[v],ed[v],0};lis[tot](node){-1,dfn[u],dfn[v],ed[v],0};lis[tot](node){1,dfn[v],ed[u]1,n,0};lis[tot](node){-1,ed[v]1,ed[u]1,n,0};}else{lis[tot](node){1,dfn[u],dfn[v],ed[v],0};lis[tot](node){-1,ed[u]1,dfn[v],ed[v],0};}}for (int il;ir;i) lis[tot](node){0,dfn[fru[i].u],dfn[fru[i].v],fru[i].k,i};sort(lis1,listot1);int lcnt0,rcnt0;for (int i1;itot;i){if (lis[i].type) bit.modify(lis[i].l,lis[i].type),bit.modify(lis[i].r1,-lis[i].type);else{int kbit.query(lis[i].l);if (lis[i].rk) L[lcnt]fru[lis[i].id];else fru[lis[i].id].k-k,R[rcnt]fru[lis[i].id];}}for (int il;illcnt-1;i) fru[i]L[i-l1];for (int illcnt;ir;i) fru[i]R[i-l-lcnt1];solve(l,llcnt-1,vl,vmid);solve(llcnt,r,vmid1,vr);
}
int main()
{nread(),pread(),qread();for (int i1;in;i){int u,v;uread(),vread();addnode(u,v),addnode(v,u);}dep[1]1,dfs(1);for (int i1;ip;i) {pan[i].aread(),pan[i].bread(),pan[i].cread();if (dfn[pan[i].a]dfn[pan[i].b]) swap(pan[i].a,pan[i].b);}sort(pan1,panp1);for (int i1;iq;i){fru[i].uread(),fru[i].vread(),fru[i].kread(),fru[i].idi;if (dfn[fru[i].u]dfn[fru[i].v]) swap(fru[i].u,fru[i].v);}solve(1,q,1,p);for (int i1;iq;i) printf(%d\n,ans[i]);return 0;
}
