下面是对20200721比赛的总结与反思

T1

这道题我直接切了

但是正解是\(O(n)\),我打的是\(O(nlogn)\)

#include
#include
#include
#define ri register int
#define Starseven main
#define mid (l+r>>1)
#define ls id<<1
#define rs id<<1|1
#define int long long
using namespace std;
const int N=5e5+20;
int read();
void write(int);
int n,t,mall,ans[N];

//----------------------------
struct node{
	int next,to,va;
}f[N];
int tail[N],k;

void Maketo(int from,int to,int va){
	f[++k].next=tail[from];tail[from]=k;f[k].to=to;f[k].va=va;
	return ;
}
//-----------------------------
//-----------------------------
bool can[N];
//-----------------------------

struct xyx{
	int deep,id,size,wson,dis,top,hsh;
}tr[N];
int cnt,sh[N];

void Dfs1(int x,int fa){
	tr[x].deep=tr[fa].deep+1;
	tr[x].size=1;
	for(ri i=tail[x];i;i=f[i].next){
		int y=f[i].to;if(y==fa) continue;
		tr[y].dis=tr[x].dis+f[i].va;
		Dfs1(y,x);
		if(!tr[x].wson||tr[tr[x].wson].size=r){
		tree[id].lazy+=k;
		return ;
	} 
	Pushdown(id);
	if(x<=mid) Change(l,mid,x,y,ls,k);
	if(y>mid) Change(mid+1,r,x,y,rs,k);
}

//-------------------------

//-------------------------
bool cmp(const xyx &a,const xyx &b){
	return a.deepmall+t*tr[i].deep){
				Change(1,n,tr[i].id,tr[i].id+tr[i].size-1,1,mall+t*tr[i].deep-gg);
				ans[tr[i].hsh]=mall+t*tr[i].deep;
			}
			else ans[tr[i].hsh]=gg;
		}
		else ans[tr[i].hsh]=gg;
	}
}

void Init(){
	freopen("climb1.in","r",stdin);
	freopen("climb.out","w",stdout);
}

signed Starseven(void){
//	Init();
	n=read(),t=read();
	for(ri i=2;i<=n;i++){
		int fa=read(),w=read(),judge=read();
		Maketo(fa,i,w);
		if(judge==1) can[i]=false;
		else can[i]=true;
	}
	Dfs1(1,0);Dfs2(1,1);
	Build_tree(1,n,1);
	sort(tr+1,tr+1+n,cmp);
	int st=1,head=1;
	mall=(-1)*t;
	while(head<=n){
		int judge=Find(1,n,tr[head].id,1)-t*tr[head].deep;
		mall=min(mall,judge);
		if(tr[head].deep==tr[head+1].deep) head++;
		else{
			Solve(st,head);
			st=head=head+1;
		}
	}
	for(ri i=1;i<=n;i++){
		write(ans[i]);puts("");
	}
	return 0;
}

int read(){
	char ch=getchar();
	int re=0,op=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') op=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		re=(re<<3)+(re<<1)+ch-'0';
		ch=getchar();
	}
	return re*op;
}

void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return ;
}

/*
4 3
1 7 1
1 5 0
2 1 0
*/

T3

不会做

留坑代填