QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#184978#7103. Red Black TreeEastKingWA 1189ms42544kbC++173.8kb2023-09-21 15:16:502023-09-21 15:16:51

Judging History

你现在查看的是最新测评结果

  • [2023-09-21 15:16:51]
  • 评测
  • 测评结果:WA
  • 用时:1189ms
  • 内存:42544kb
  • [2023-09-21 15:16:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
typedef long long ll;
int n;
bool red[M];
vector<pair<int,ll>>G[M],E[M];
int tot,dfn[M],fa[20][M],dep[M];
int bel[M];
ll val[M];
int lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	int tmp=dep[y]-dep[x];
	for(int i=0;tmp;i++){
		if(tmp&1)y=fa[i][y];
		tmp>>=1;
	}
	if(x==y)return x;
	for(int i=19;i>=0;i--){
		if(fa[i][x]==fa[i][y])continue;
		x=fa[i][x];
		y=fa[i][y];
	}
	return fa[0][x];
}
void init(){//dfn+倍增 
	tot=0;
	function<void(int,int)>dfs=[&](int x,int f){
		if(red[x])bel[x]=x;
		dfn[x]=++tot;
		dep[x]=dep[f]+1;
		fa[0][x]=f;
		for(int i=1;i<20;i++)fa[i][x]=fa[i-1][fa[i-1][x]];
		for(auto [y,w]:G[x]){
			if(y==f)continue;
			val[y]=val[x]+w;
			bel[y]=bel[x];
			dfs(y,x);
		}
	};
	bel[1]=1;
	val[1]=0;
	dfs(1,0);
}
ll get_val(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	return val[a]-val[b];
}
bool mark[M];//记录 
int build(vector<int>&Q){
	//排序+去重 
	sort(Q.begin(),Q.end(),[&](int a,int b){return dfn[a]<dfn[b];});
	Q.erase(unique(Q.begin(),Q.end()),Q.end());
	//求虚树点+连边 
	int len=Q.size();
	vector<int>stk(len*2+1);
	int top=0;
	stk[++top]=Q[0];
	for(int i=1;i<len;i++){
		int now=Q[i];
		int lc=lca(now,stk[top]);
		while(dep[lc]<dep[stk[top-1]]){
			E[stk[top-1]].push_back({stk[top],get_val(stk[top-1],stk[top])});
			top--;
		}
		if(dep[lc]>dep[stk[top-1]]){
			if(lc==stk[top]){
				stk[++top]=now;
			}else{ 
				E[lc].push_back({stk[top],get_val(lc,stk[top])});
				stk[top]=lc;
				stk[++top]=now;
			}
		}else if(lc==stk[top-1]){
			E[stk[top-1]].push_back({stk[top],get_val(stk[top-1],stk[top])});
			stk[top]=now;
		}
	}
	while(top>1){
		E[stk[top-1]].push_back({stk[top],get_val(stk[top-1],stk[top])});
		top--;
	}
	return stk[top];//返回树根 
}
ll mxe[M],mxv[M];
int Lt[M],Rt[M],tid[M],tcnt;
ll mxL[M],mxR[M];
void dfs(int x){//树形dp 
	mxe[x]=-1e18;
	mxv[x]=0;
	Lt[x]=++tcnt;
	tid[tcnt]=x;
	for(auto [y,w]:E[x]){
		dfs(y);
		mxv[x]=max(mxv[x],mxv[y]);
		if(!red[y]){
			mxe[x]=max(mxe[x],mxe[y]+w);
		}
	}
	if(mark[x]){
		mxe[x]=max(mxe[x],0ll);
	}
	if(red[x]){
		mxv[x]=max(mxv[x],mxe[x]);
	}
	Rt[x]=tcnt;
}
ll Ans;
void clear(int x){//清空虚树边 
	mark[x]=0;
	//printf("x=%d mxe=%lld other=%lld\n",x,mxe[x],max(mxL[Lt[x]-1],mxR[Rt[x]+1]));
	Ans=min(Ans,max(max(mxe[x],mxv[x]),max(mxL[Lt[x]-1],mxR[Rt[x]+1])));
	for(auto [y,w]:E[x]){
		clear(y);
	}
	E[x].clear();
}
int main(){
	int cas;
	scanf("%d",&cas);
	while(cas--){
		int m,q;
		scanf("%d %d %d",&n,&m,&q);
		//clear
		for(int i=1;i<=n;i++){
			red[i]=0;
			G[i].clear();
		}
		//
		for(int i=1;i<=m;i++){
			int x;
			scanf("%d",&x);
			red[x]=1;
		}
		for(int i=1;i<n;i++){
			int a,b,c;
			scanf("%d %d %d",&a,&b,&c);
			G[a].push_back({b,c});
			G[b].push_back({a,c});
		}
		init();//dfs+倍增
		while(q--){
			int k;
			scanf("%d",&k);
			//读入关键点 
			vector<int>Q(k);
			for(int i=0;i<k;i++){
				int x;
				scanf("%d",&Q[i]);
				mark[Q[i]]=1;//记录关键点信息 
			}
			//建虚树+树形dp 
			int rt=build(Q);
			tcnt=0;
			dfs(rt);
			mxL[0]=0,mxR[tcnt+1]=0; 
			for(int i=1;i<=tcnt;i++){
				mxL[i]=mxL[i-1];
				int x=tid[i];
				if(mark[x]){
					//printf("x=%d v=%lld\n",x,val[x]-val[bel[x]]);
					mxL[i]=max(mxL[i],val[x]-val[bel[x]]);
				}
			}
			for(int i=tcnt;i>=1;i--){
				mxR[i]=mxR[i+1];
				int x=tid[i];
				if(mark[x]){
					mxR[i]=max(mxR[i],val[x]-val[bel[x]]);
				}
			}
			Ans=mxR[1];
			clear(rt);//记得清空 
			//printf("ans:");
			printf("%lld\n",Ans);
		}
	}
	return 0;
}
/*
2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 19060kb

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: -100
Wrong Answer
time: 1189ms
memory: 42544kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

wrong answer 427th lines differ - expected: '1455744935', found: '1637098612'