首页 > 其他分享 >[USACO11DEC]Grass Planting G

[USACO11DEC]Grass Planting G

时间:2023-05-14 15:24:22浏览次数:33  
标签:Planting ch int read qrw USACO11DEC Grass id define

树链剖分题目
注意:

  1. 要把边权转为点权
  2. 计算两条链时,这两条链的公共点被额外算了一次,需要减去它
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<algorithm>
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{
    typedef __uint128_t ULLL;
    static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    inline void pc(const char &ch){
    	if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
    	*pw++=ch;
	}
    #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
	struct FastMod{
        FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){}
        ULL reduce(ULL a){
            ULL q=(ULL)((ULLL(m)*a)>>64);
            ULL r=a-q*b;
            return r>=b?r-b:r;
        }
        ULL b,m;
    }HPOP(10);
    struct QIO{
    	char ch;
    	int st[40];
    	inline char read(){
    		ch=gc;
    		if(ch<'A'||ch>'Z')ch=gc;
    		return ch;
		}
		inline void read(int &x){
    		x=0,ch=gc;
    		while(!isdigit(ch))ch=gc;
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
		}
		template<class T>inline void write(T a){
			do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
			pc('\n');
		}
	}qrw;
}
using namespace FastIo;
#define NUMBER1 200000
#define P(A) A=-~A
#define fione_i(begin,end) for(register int i=begin;i<=end;P(i))
#define ls(rt) rt<<1
#define rs(rt) rt<<1|1
#define mid (l+r>>1)
#define lson l,mid,ls(rt)
#define rson mid+1,r,rs(rt)
#define sz (r-l+1)
#define tt(u) for(register int i=head[u];i;i=e[i].next) 
struct EDGE{int next,to;}e[(NUMBER1<<1)+5];
int depth[NUMBER1+5],size[NUMBER1+5],son[NUMBER1+5],fa[NUMBER1+5],n,head[NUMBER1+5],tot(0),cnt(0),id[NUMBER1+5],top[NUMBER1+5];
struct Segment{
	int tree[(NUMBER1<<2)+5],lazy[(NUMBER1<<2)+5];
	inline void push_up(const int &rt){tree[rt]=tree[ls(rt)]+tree[rs(rt)];}
	inline void change(int l,int r,int rt,int date){tree[rt]+=date*sz,lazy[rt]+=date;}
	inline void push_down(int l,int r,int rt){
		change(lson,lazy[rt]);change(rson,lazy[rt]);
		lazy[rt]=0;
	}
	void intervaland(int l,int r,int rt,int x,int y,int date){
		if(x<=l&&r<=y)return tree[rt]+=sz*date,lazy[rt]+=date,void();
		if(lazy[rt])push_down(l,r,rt);
		if(x<=mid)intervaland(lson,x,y,date);
		if(mid<y)intervaland(rson,x,y,date);
		push_up(rt); 
	}
	int intervalsum(int l,int r,int rt,int x,int y){
		if(x<=l&&r<=y)return tree[rt];
		if(lazy[rt])push_down(l,r,rt);
		int res(0);
		if(x<=mid)res+=intervalsum(lson,x,y);
		if(mid<y)res+=intervalsum(rson,x,y);
		return res;
	}
}seg;
inline void add(const int &u,const int &v){e[++tot].next=head[u];e[tot].to=v,head[u]=tot;}
void dfs1(int u,int fath,int deep){
	depth[u]=deep,fa[u]=fath,size[u]=1;
	int ms(-1); 
	tt(u){
		if(e[i].to==fath)continue;
		dfs1(e[i].to,u,deep+1);
		size[u]+=size[e[i].to];
		if(size[e[i].to]>ms)ms=size[e[i].to],son[u]=e[i].to; 
	}
}
void dfs2(int u,int tf){
	id[u]=++cnt,top[u]=tf;
	if(!son[u])return;
	dfs2(son[u],tf);
	tt(u){
		if(e[i].to==fa[u]||e[i].to==son[u])continue;
		dfs2(e[i].to,e[i].to);
	}
}
inline void treeand(int x,int y){
	while(top[x]!=top[y]){
		if(depth[top[x]]<depth[top[y]])std::swap(x,y);
		seg.intervaland(1,n,1,id[top[x]],id[x],1);
		x=fa[top[x]];
	}
	if(depth[x]>depth[y])std::swap(x,y);
	seg.intervaland(1,n,1,id[x],id[y],1);
	seg.intervaland(1,n,1,id[x],id[x],-1);
}
inline int treesum(int x,int y){
	int ans(0);
	while(top[x]!=top[y]){
		if(depth[top[x]]<depth[top[y]])std::swap(x,y);
		ans+=seg.intervalsum(1,n,1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(depth[x]>depth[y])std::swap(x,y);
	ans+=seg.intervalsum(1,n,1,id[x],id[y]);
	ans-=seg.intervalsum(1,n,1,id[x],id[x]);
	return ans;
}
signed main(){
	int m,x,y;
	char sb;
	qrw.read(n);
	qrw.read(m);
	fione_i(2,n){
		qrw.read(x);
		qrw.read(y);
		add(x,y);add(y,x);
	}
	dfs1(1,0,1);
	dfs2(1,1);
	while(m--){
		sb=qrw.read();
		qrw.read(x);
		qrw.read(y);
		if(sb=='P')treeand(x,y);
		else qrw.write(treesum(x,y));
	}
	fsh;
    exit(0);
    return 0;
}

标签:Planting,ch,int,read,qrw,USACO11DEC,Grass,id,define
From: https://www.cnblogs.com/SHOJYS/p/17399357.html

相关文章

  • 2022CCPC Weihai Site C. Grass
    C.Grass题意:选出5个点,并以A点为中心不存在与其他4个点的向量同向且共线分析:预选出4个点,枚举第5个点如果遍历一遍后没有找到能与选定的4个点不都同向共线,此时一定满足所有的点都共线(所有点都不满足)当选出满足条件的点后再去判断以那个点为中心去连接其他点不会有共线的情......
  • GrassRouter多链路聚合通信系统保障公路网络稳定全面覆盖解决方案
    近年来国内经济不断发展,城市道路交通能力迅速提高,各省市道路交通体系不断完善,促使高速公路运能得到极大提高,公路运输的通达性、舒适性得到明显提高。随着现代化高速公路的建设,新一代无线网络监控系统,已日益成为高速公路监控管理的主要手段。目前高速公路普遍存在各路段监控“信息孤......
  • Grasshopper - Summation
    SummationWriteaprogramthatfindsthesummationofeverynumberfrom1tonum.Thenumberwillalwaysbeapositiveintegergreaterthan0.Forexample(Inp......
  • Grasshopper - Personalized Message
    InstructionsCreateafunctionthatgivesapersonalizedgreeting.Thisfunctiontakestwoparameters:nameandowner.Useconditionalstoreturntheproperme......
  • P3119 [USACO15JAN]Grass Cownoisseur G 题解
    做过的原题,模拟赛时PDF里的题面实在有点难受。首先有显然结论:在一个环上反走一定是不值的,因为环上的点本来就相互可达。所以考虑缩点。缩点后的问题可以看成:求对于每一......
  • Grassfire算法- 运动规划(Motion planning)
     Grassfire算法:一、概念这个算法是做图像处理的抽骨架处理,目的是求出图像的骨架,可以想象一片与物体形状相同的草,沿其外围各点同时点火。当火势向内蔓延,向前推进的火线相遇......
  • PrograssBar控件
    常用属性:Value,Step,Style,MarqueeAnimationSpeed,Maximum,Minimum方法:PerformStep()Increment() 知识点1:Style控制PrograssBar的样式,选项为:Block,Continuous,Marquee当Style=Ma......