QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178708#7103. Red Black TreePlentyOfPenalty#TL 3ms13056kbC++204.3kb2023-09-14 11:24:022023-09-14 11:24:02

Judging History

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

  • [2023-09-14 11:24:02]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:13056kb
  • [2023-09-14 11:24:02]
  • 提交

answer

#include<bits/stdc++.h>
#ifndef memset0
	#define endl '\n'
#endif
using namespace std;
const int N=1e5+9;
int T,n,m,q,tot,anc[N],fa[N],dfn[N],dep[N],a[N],b[N],top[N],cur[N],siz[N],son[N],rnkl[N],rnkr[N];
long long len[N],dp[N][2],pre[N],suf[N];
bool col[N],foc[N];
vector<int> red,F[N];
vector<pair<int,int>> G[N];
template<class T> inline void updmin(T &x,T y){
	if(y<x)x=y;
}
template<class T> inline void updmax(T &x,T y){
	if(y>x)x=y;
}
inline int cmp_by_dfn(int u,int v){
	return dfn[u]<dfn[v];
}
// int jp[N][20];
// inline int lca(int u,int v){
// 	// cerr<<"lca "<<u<<" "<<v<<" "<<dep[u]<<" "<<dep[v]<<endl;
// 	if(dep[u]>dep[v])swap(u,v);
// 	for(int i=19;i>=0;i--)
// 		if(jp[v][i]&&dep[jp[v][i]]>=dep[u]){
// 			v=jp[v][i];
// 		}
// 	if(u==v)return u;
// 	for(int i=19;i>=0;i--)
// 		if(jp[u][i]&&jp[v][i]&&jp[u][i]!=jp[v][i]){
// 			u=jp[u][i];
// 			v=jp[v][i];
// 		}
// 	return jp[u][0];
// }
void dfs(int u,int u_anc){
	if(col[u]){
		u_anc=u;
	}
	dfn[u]=++tot;
	anc[u]=u_anc;
	siz[u]=1;
	son[u]=0;
	// cerr<<"!!! dfs "<<u<<" "<<u_anc<<endl;
	for(auto [v,w]:G[u])
		if(v!=fa[u]){
			// cerr<<u<<" >> "<<v<<endl;
			fa[v]=u;
			dep[v]=dep[u]+1;
			len[v]=len[u]+w;
			dfs(v,u_anc);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]]){
				son[u]=v;
			}
		}
}
void dfs2(int u,int tpt){
	top[u]=tpt;
	if(siz[u]==1)return;
	dfs2(son[u],tpt);
	for(auto [v,w]:G[u])
		if(v!=fa[u]&&v!=son[u]){
			dfs2(v,v);
		}
}
inline int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		v=fa[top[v]];
	}
	return dep[u]<dep[v]?u:v;
}
void solve(int u){
	dp[u][0]=dp[u][1]=0;
	rnkl[u]=rnkr[u]=cur[u];
	if(foc[u]){
		dp[u][0]=len[u];
	}
	for(int v:F[u]){
		solve(v);
		updmax(dp[u][1],dp[v][1]);
		if(dep[anc[v]]<dep[u]){
			updmax(dp[u][0],dp[v][0]);
		}else{
			updmax(dp[u][1],dp[v][0]-len[anc[v]]);
		}
		updmin(rnkl[u],rnkl[v]);
		updmax(rnkr[u],rnkr[v]);
	}
	if(col[u]){
		updmax(dp[u][1],dp[u][0]-len[u]);
		dp[u][0]=0;
	}
	// cerr<<"dp["<<u<<"] :: "<<dp[u][0]<<" "<<dp[u][1]<<endl;
}
int main(){
#ifdef memset0
	freopen("B.in","r",stdin);
#endif
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>q;
		fill_n(col+1,n,false);
		for(int i=1;i<=n;i++){
			G[i].clear();
		}
		for(int x,i=1;i<=m;i++){
			cin>>x;
			red.push_back(x);
			col[x]=true;
		}
		for(int u,v,w,i=1;i<n;i++){
			cin>>u>>v>>w;
			// cerr<<"! "<<u<<" "<<v<<" "<<w<<endl;
			G[u].emplace_back(v,w);
			G[v].emplace_back(u,w);
		}
		// exit(0);
		tot=0;
		dep[1]=1;
		dfs(1,1);
		dfs2(1,1);
		// for(int i=1;i<=n;i++){
		// 	jp[i][0]=fa[i];
		// }
		// for(int j=1;j<20;j++)
		// 	for(int i=1;i<=n;i++){
		// 		jp[i][j]=jp[jp[i][j-1]][j-1];
		// 	}
		// for(int i=1;i<=n;i++)cerr<<son[i]<<" \n"[i==n];
		// for(int i=1;i<=n;i++)cerr<<siz[i]<<" \n"[i==n];
		// for(int i=1;i<=n;i++)cerr<<top[i]<<" \n"[i==n];
		for(int k,i=1;i<=q;i++){
			cin>>k;
			for(int i=1;i<=k;i++)cin>>b[i];
			sort(b+1,b+k+1,cmp_by_dfn);
			a[tot=1]=1;
			for(int i=1;i<=k;i++){
				a[++tot]=b[i];
				// cerr<<"! "<<b[i]<<" "<<lca(b[i-1],b[i])<<endl;
				if(i>1)a[++tot]=lca(b[i-1],b[i]);
			}
			sort(a+1,a+tot+1,cmp_by_dfn);
			tot=unique(a+1,a+tot+1)-a-1;
			for(int i=1;i<=tot;i++){
				cur[a[i]]=i;
				foc[a[i]]=false;
				F[a[i]].clear();	
			}
			for(int i=1;i<=k;i++){
				foc[b[i]]=true;
			}
			// cerr<<"  A ";for(int i=1;i<=tot;i++)cerr<<a[i]<<" \n"[i==tot];
			// cerr<<"DFN ";for(int i=1;i<=tot;i++)cerr<<dfn[a[i]]<<" \n"[i==tot];
			// cerr<<"FOC ";for(int i=1;i<=tot;i++)cerr<<foc[a[i]]<<" \n"[i==tot];
			for(int lc,i=1;i<tot;i++){
				lc=lca(a[i],a[i+1]);
				F[lc].push_back(a[i+1]);
			}
			solve(1);
			for(int i=1;i<=tot;i++){
				pre[i]=pre[i-1];
				if(foc[a[i]]){
					updmax(pre[i],len[a[i]]-len[anc[a[i]]]);
				}
			}
			suf[tot+1]=0;
			for(int i=tot;i>=1;i--){
				suf[i]=suf[i+1];
				if(foc[a[i]]){
					updmax(suf[i],len[a[i]]-len[anc[a[i]]]);
				}
			}
			long long ans=LLONG_MAX;
			for(int i=1;i<=tot;i++){
				int u=a[i];
				long long cur=dp[u][1];
				updmax(cur,dp[u][0]-len[u]);
				if(rnkl[u]>1){
					updmax(cur,pre[rnkl[u]-1]);
				}
				if(rnkr[u]<tot){
					updmax(cur,suf[rnkr[u]+1]);
				}
				ans=min(ans,cur);
				// cerr<<"ans["<<u<<"] :: "<<cur<<endl;
			}
			cout<<ans<<endl;
		}
	}
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 13056kb

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
Time Limit Exceeded

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: