品牌外贸网站建设,海淀专业企业网站建设,php学多久可以做网站,wordpress .htaccess 固定链接正题
题目链接:https://jzoj.net/senior/#main/show/3910 题目大意 nnn个点的森林mmm个操作#xff0c;
合并两棵树让xxx节点到根节点的路径标记上cntcntcnt。并让cntcntcnt查询一个节点xxx是否有标记yyy。 解题思路
这里考虑离线的算法。我们可以先将这个森林的最终状态构…正题
题目链接:https://jzoj.net/senior/#main/show/3910 题目大意
nnn个点的森林mmm个操作
合并两棵树让xxx节点到根节点的路径标记上cntcntcnt。并让cntcntcnt查询一个节点xxx是否有标记yyy。 解题思路
这里考虑离线的算法。我们可以先将这个森林的最终状态构建出来每条边的边权表示上一个标记的编号。然后我们发现个查询需要满足两个条件
查询节点xxx是该标记起始点yyy的祖先。x−yx-yx−y的路径上最大边权比该标记小。
这里用树上倍增的方法计算即可。时间复杂度O(nlogn)O(n\log n)O(nlogn)。加上快读可以卡过
正解好像是O(α(n)n)O(\alpha (n)n)O(α(n)n)搜索树这里就不具体写了。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecctype
#includevector
using namespace std;
const int N5e5100;
struct node{int to,next,w;
}a[N];
int tot,cnt,z,num,n,m,f[N][20],v[N][20],dep[N];
int ls[N],rfn[N],ed[N],p[N],ask[N],in[N];
bool ans[N];
vectorint q[N];
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;
}
int read() {int x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
void dfs(int x)
{rfn[x]cnt;for(int ils[x];i;ia[i].next){int ya[i].to;dep[y]dep[x]1;f[y][0]x;v[y][0]a[i].w;dfs(y);}ed[x]cnt;return;
}
int LCA(int x,int y)
{int z0;for(int i19;i0;i--)if(dep[f[y][i]]dep[x])zmax(v[y][i],z),yf[y][i];return z;
}
int main()
{//freopen(data.in,r,stdin);//freopen(data.out,w,stdout);nread();mread();for(int i1;im;i){int op,x,y;opread();if(op1){xread();yread();in[x];addl(y,x,z);}if(op2)p[z]read();if(op3){ask[num]read();q[read()].push_back(num);}}for(int i1;in;i)if(!in[i]) dep[i]1,dfs(i);for(int j1;j20;j)for(int i1;in;i)f[i][j]f[f[i][j-1]][j-1],v[i][j]max(v[i][j-1],v[f[i][j-1]][j-1]);for(int i1;iz;i){for(int j0;jq[i].size();j){int xask[q[i][j]],yp[i];if(rfn[x]rfn[y]ed[x]rfn[y]LCA(x,y)i)ans[q[i][j]]1;}}for(int i1;inum;i)if(ans[i]) puts(YES);else puts(NO);
}
