首页 > 其他分享 >板子

板子

时间:2023-08-20 22:23:57浏览次数:24  
标签:Node ... struct int tree 板子

LCT

struct LinkCutTree {
   struct Node {
      int ch[2]; 
      int fa; 
      int rev_tag; 
      // ...
   }; 
   
   vector<Node> tree; 
   
   map<pair<int, int>, bool> edge; 
   
   void init(int n /* ... */) {
      tree.resize(n + 10); 
      for (int i = 1; i <= n; ++i) {
         tree[i].ch[0] = tree[i].ch[1] = tree[i].fa = tree[i].rev_tag = 0; 
         // ...
   	}
   }
   
   void pushUp(int x) {
      // ...
   }
   
   void pushDown(int x) {
      if (tree[x].rev_tag) {
         swap(tree[tree[x].ch[0]].ch[0], tree[tree[x].ch[0]].ch[1]); 
         tree[tree[x].ch[0]].rev_tag ^= 1; 
         swap(tree[tree[x].ch[1]].ch[0], tree[tree[x].ch[1]].ch[1]); 
         tree[tree[x].ch[1]].rev_tag ^= 1; 
         tree[x].rev_tag = 0; 
      }
      // ...
   }
   
   int get(int x) { return tree[tree[x].fa].ch[1] == x; }
   
   int isRoot(int x) { return tree[tree[x].fa].ch[0] != x && tree[tree[x].fa].ch[1] != x; }
   
   void rotate(int x) {
      int y = tree[x].fa, z = tree[y].fa, t = get(x); 
      if (!isRoot(y)) tree[z].ch[get(y)] = x; 
      tree[y].ch[t] = tree[x].ch[t ^ 1], tree[tree[x].ch[t ^ 1]].fa = y; 
      tree[x].ch[t ^ 1] = y, tree[y].fa = x; 
      tree[x].fa = z; 
      pushUp(y); 
   }
   
   void update(int x) {
      if (!isRoot(x)) update(tree[x].fa); 
      pushDown(x); 
   }
   
   void splay(int x) {
      update(x); 
      for (int fa = tree[x].fa; !isRoot(x); rotate(x), fa = tree[x].fa) {
         if (!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x); 
      }
      pushUp(x);  
   }
   
   int access(int x) {
      splay(x); 
      tree[x].ch[1] = 0, pushUp(x); 
      while (tree[x].fa) {
         int fa = tree[x].fa; 
         splay(fa), tree[fa].ch[1] = x, pushUp(fa); 
         x = fa; 
      }
      return x; 
   }
   
   void makeRoot(int x) {
      access(x), splay(x); 
      swap(tree[x].ch[0], tree[x].ch[1]); 
      tree[x].rev_tag ^= 1; 
   }
   
   int findRoot(int x) {
      x = access(x); 
      pushDown(x); 
      while (tree[x].ch[0]) x = tree[x].ch[0], pushDown(x); 
      splay(x); 
      return x; 
   }
   
   void link(int x, int y) {
      if (findRoot(x) == findRoot(y)) return; 
      makeRoot(x), tree[x].fa = y; 
      edge[make_pair(x, y)] = edge[make_pair(y, x)] = 1; 
   }
   
   void cut(int x, int y) {
      if (!edge[make_pair(x, y)]) return; 
      makeRoot(x), access(x), splay(y), tree[y].fa = 0; 
      edge[make_pair(x, y)] = edge[make_pair(y, x)] = 0; 
   }
   
   int split(int x, int y) {
      makeRoot(x); 
      return access(y); 
   }
   
   // ...
} LCT;

标签:Node,...,struct,int,tree,板子
From: https://www.cnblogs.com/zzzYheng/p/17644728.html

相关文章

  • 平衡树板子
    替罪羊#include<algorithm>#include<iostream>usingnamespacestd;constintMaxN=4e5+10;constdoubleeps=0.75;intd[MaxN],l[MaxN],r[MaxN],cnt[MaxN],sum[MaxN],sz[MaxN],a[MaxN],tot,n,root,len;voidupdate(intx){//更新......
  • 二分板子
    1.求最大值最小while(l<=r){  mid=(l+r)>>1;  if(check(mid))ans=mid,r=mid-1;    elsel=mid+1; }例题洛谷p3853路标设置code#include<bits/stdc++.h>usingnamespacestd;intl,n,k,a[100010],r,ll,mid,ans,cnt;boolcheck......
  • 计算几何の板子
    一精度处理\(eps\)和\(sgn\)constdoubleeps=1e-8;intsgn(doublex){//判断大小if(fabs(x)<eps)return0;elsereturnx<0?-1:1;}二点1点的初始化向量的表示形式上与点完全相同重载点运算符,支持向量的四种运算structPoint{doublex,y;Poi......
  • 常用板子
    树状数组点击查看代码intc[N];intask(intx){intres=0;for(;x;x-=x&-x)ans+=c[i];returnans;}voidadd(inti,intx){for(;x<=n;x+=x&-x)c[x]+=y;}intpre(intl,intr){returnask(r)-ask(l-1);}......
  • Arduino官方推出两款H747板子,Portenta H7和Portenta Carrier
    这几天的CES2020上,Arduino亮相两款新板子。PortentaH7原理图和引脚图:Arduino-PortentaH7-schematic-V1.0.pdfPinout-PortentaH7_v3.pdf软件方面:1、编程支持Arduinocode,Python和JavaScript。2、基于MbedOS的Arduino框架。3、原生支持MbedAPI。4、AI方面支持TensorFlowLit......
  • 数论板子
    exgcd点击查看代码__int128exgcd(__int128as,__int128bs,__int128&x,__int128&y){if(bs==0){x=1;y=0;returnas;}__int128ans=exgcd(bs,as%bs,y,x);y-=(as/bs)*x;returnans;}a&c&lucas点击查看代码......
  • 【调试笔记】韦东山:在100ASK_IMX6ULL板子上支持其他型号的屏幕
    论  坛:http://bbs.100ask.net/(学术答疑)公 众 号:百问科技版本日期作者说明V12020韦东山技术文档在100ASK_IMX6ULL板子上支持其他型号的屏幕1.在100ASK_IMX6ULL底板上如何接其他厂家的屏幕很多学员有过STM32的学习经验,他们手上的开发板很多,LCD也很多。一个LCD还挺贵的,不能浪......
  • 板子哲学汇总
    密码:#39C5BB树状数组tarjandfs序求lca,RMQ高斯消元组合数学(CRT,lucas)分块与莫队......
  • EP3C40F484C8N+cyusb3014 该板子之前批量过,现在没有板子了,只有完整的开发资料。
    EP3C40F484C8N+cyusb3014该板子之前批量过,现在没有板子了,只有完整的开发资料。包含FPGA源码,usb源码。资料里有原理图和pcbID:5730605186874401......
  • 板子
    板子博主线上考试自己用的板子。快读charbuf[1<<21],*p1=buf,*p2=buf,obuf[1<<21],*O=obuf;#definegetchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)计数题取模inlineintadd(intx){return(x>=mod)?x-mod:x;}inlinevoida......