求助树剖
  • 板块P4114 Qtree1
  • 楼主剑雪清寒
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/7/8 20:18
  • 上次更新2023/10/27 21:26:52
查看原帖
求助树剖
214728
剑雪清寒楼主2022/7/8 20:18

找不出错咧,WA 求助(

#include <bits/stdc++.h>
inline int read() {
	int x,f;char ch;
	for(f=0;!isdigit(ch=getchar());f=ch=='-');
	for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
	return f?-x:x; 
}
inline void print(long long x,char las) {
	if(!x) {
		putchar(48),putchar(las);
		return ;
	}
	if(x<0) putchar('-'),x=-x;
	int ls[23],k=0;
	while(x) ls[++k]=x%10,x/=10;
	while(k) putchar(ls[k--]+48);
	putchar(las);
	return ;
}
struct road{
	int u,v;
}rrdd[100001];
int rd_sum=0;
struct edge {
	int to,len;
	edge *next;
}rd[200000];
edge *head[100001];
struct node {
	int value=0,wson=0,size=1,top=0,dfn=0,deep=0,dad=0;
}nd[100001];
struct tree {
	int cnt,pre[100001],ss=0;
	int lson[400001],rson[400001],va[400001];
	inline void update(int x) { va[x]=va[lson[x]]>va[rson[x]] ? va[lson[x]] : va[rson[x]]; }
	inline void build(int x,int l,int r) {
		ss++;
		if(l==r) {
			va[x]=pre[l];
			return ;
		}
		int mid=(l+r)>>1;
		lson[x]=ss+1;
		build(ss+1,l,mid);
		rson[x]=ss+1;
		build(ss+1,mid+1,r);
		update(x);
		return ;
	}
	inline void replace(int x,int l,int r,int now,int re) {
		if(l>now || r<now) return ;
		if(l==r) {
			va[x]=re;
			return ;
		}
		int mid=(l+r)>>1;
		replace(lson[x],l,mid,now,re);
		replace(rson[x],mid+1,r,now,re);
		update(x);
		return ;
	}
	inline int find(int x,int l,int r,int L,int R) {
		if(R<L) return 0;
		if(l>R || r<L) return 0;
		if(l>=L && r<=R) return va[x];
		int mid=(l+r)>>1;
		return std::max(find(lson[x],l,mid,L,R),find(rson[x],mid+1,r,L,R)); 
	}
}tr1;
inline void dfs1(int x,int dep) {
	nd[x].deep=dep;
	for(edge *i=head[x];i!=NULL;i=i->next) {
		int nex=i->to;
		if(nd[nex].deep) continue;
		nd[nex].value=i->len;
		nd[nex].dad=x;
		dfs1(nex,dep+1);
		nd[x].size+=nd[nex].size;
		if(nd[nex].size>nd[nd[x].wson].size) nd[x].wson=nex;
	}
	return ;
}
inline void dfs2(int x,int tp) {
	nd[x].dfn=++tr1.cnt,tr1.pre[tr1.cnt]=nd[x].value;nd[x].top=tp;
	if(nd[x].wson) dfs2(nd[x].wson,tp);
	for(edge *i=head[x];i!=NULL;i=i->next) {
		int nex=i->to;
		if(nd[nex].dfn) continue;
		dfs2(nex,nex);
	}
	return ;
}
int n=read();
inline void change(int i,int t) {
	i=nd[rrdd[i].u].deep>nd[rrdd[i].v].deep ? rrdd[i].u : rrdd[i].v;
	tr1.replace(1,1,tr1.cnt,nd[i].dfn,t);
	return ;
}
inline void query(int u,int v) {
	int ans=0;
	while(nd[u].top!=nd[v].top) {
		if(nd[nd[u].top].deep<nd[nd[v].top].deep) std::swap(u,v);
		int as=tr1.find(1,1,tr1.cnt,nd[nd[u].top].dfn,nd[u].dfn);
		if(as>ans) ans=as;
		u=nd[nd[u].top].dad;
	}
	if(nd[u].deep>nd[v].deep) std::swap(u,v);
	int as=tr1.find(1,1,tr1.cnt,nd[u].dfn+1,nd[v].dfn);
	if(as>ans) ans=as;
	print(ans,'\n');
	return ;
} 
int main() {
	for(int i=1;i<n;i++) {
		int u=read(),v=read();
		rrdd[i].u=u,rrdd[i].v=v;
		rd[rd_sum].len=read();rd[rd_sum].to=v;rd[rd_sum].next=head[u];head[u]=&rd[rd_sum++];
		rd[rd_sum].len=rd[rd_sum-1].len;rd[rd_sum].to=u;rd[rd_sum].next=head[v];head[v]=&rd[rd_sum++];
	}
	dfs1(1,1);
	dfs2(1,1);
	tr1.build(1,1,tr1.cnt);
	std::string s1;
	while(std::cin>>s1) {
		if(s1=="DONE") return 0;
		if(s1=="CHANGE") change(read(),read());
		else query(read(),read());
	}
	return 0;
}

2022/7/8 20:18
加载中...