QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692564#5439. Meet in the MiddlewdnmdwrnmmpWA 0ms17488kbC++144.3kb2024-10-31 14:42:532024-10-31 14:42:59

Judging History

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

  • [2024-10-31 14:42:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:17488kb
  • [2024-10-31 14:42:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

using i64=unsigned long long;
void chmax(i64 &x,i64 y){
	if(y>x){
		x=y;
	}
}

const int N=1e5+5;
int n;
namespace tree0{
	vector<pi> G[N];
	int dfn[N], dfc;
	i64 dep[N];
	int mn[17][N];
	
	void link(int u,int v,int w){
		G[u].pb(v, w);
		G[v].pb(u, w);
	}
	void dfs(int u,int p){
		dfn[u]=++dfc;
		mn[0][dfc]=p;
		for(auto [v,w]:G[u]){
			if(v!=p){
				dep[v]=dep[u]+w;
				dfs(v, u);
			}
		}
	}
	int get(int u,int v){
		return dfn[u]<dfn[v]? u: v;
	};
	void init(){
		dfs(1, 0);
		rep(i,1,16){
			rep(j,1,n-(1<<i)+1){
				mn[i][j]=get(mn[i-1][j], mn[i-1][j+(1<<(i-1))]);
			}
		}
	}
	int LCA(int u,int v){
		if(u==v){
			return u;
		}
		if((u=dfn[u])>(v=dfn[v])){
			swap(u, v);
		}
		int lg=__lg(v-(u++));
		return get(mn[lg][u], mn[lg][v-(1<<lg)+1]);
	}
	i64 dis(int u,int v){
		return dep[u]+dep[v]-dep[LCA(u,v)]*2;
	}

	void clear(int n){
		rep(i,1,n){
			G[i].clear();
		}
		dfc=0;
	}
}
namespace tree1{
	vector<pi> G[N], Q[N];
	i64 ans[500005];
	bool vis[N];

	void link(int u,int v,int w){
		G[u].pb(v,w);
		G[v].pb(u,w);
	}
	int sz[N], totsz, hv;
	i64 dep[N];
	vi tmp;
	void dfs0(int u,int p){
		sz[u]=1;
		int mxsz=0;
		for(const auto &[v,w]:G[u]){
			if(v!=p && !vis[v]){
				dfs0(v, u);
				sz[u]+= sz[v];
				mxsz=max(mxsz, sz[v]);
			}
		}
		mxsz=max(mxsz, totsz-sz[u]);
		if(mxsz*2<=totsz){
			hv=u;
		}
	}
	void dfs1(int u,int p){
		tmp.pb(u);
		for(const auto &[v,w]:G[u]){
			if(v!=p && !vis[v]){
				dep[v]=dep[u]+w;
				dfs1(v, u);
			}
		}
	}
	i64 dis(int u,int v){
		return tree0::dis(u, v)+dep[u]+dep[v];
	}

	vector< tuple<int,int,i64> > prt, srt;
	vector<vi> S;

	void slv(int u){
		dfs0(u, 0);
		u=hv;
		vis[u]=1;

		prt.clear();
		srt.clear();
		S.clear();
		S.pb((vi){u});

		dep[u]=0;
		for(auto [v,w]:G[u]){
			if(!vis[v]){
				dep[v]=w;
				dfs1(v, u);
				S.resize(S.size()+1);
				swap(S.back(), tmp);
			}
		}
		prt.resize(S.size());
		rep(i,0,(int)S.size()-1){
			int du=S[i][0], dv=S[i][0];
			i64 ddis=0;
			for(int x:S[i]){
				i64 d0=dis(du, x), d1=dis(dv, x);
				if(d0<d1){
					swap(d0, d1);
					swap(du, dv);
				}
				if(d0>ddis){
					ddis=d0;
					dv=x;
				}
			}
			prt[i]={du, dv, ddis};
		}
		srt=prt;
		rep(i,1,(int)S.size()-1){
			auto &[du,dv,ddis]=prt[i];
			for(int x:{get<0>(prt[i-1]), get<1>(prt[i-1])}){
				i64 d0=dis(du, x), d1=dis(dv, x);
				if(d0<d1){
					swap(d0, d1);
					swap(du, dv);
				}
				if(d0>ddis){
					ddis=d0;
					dv=x;
				}
			}
		}
		per(i,(int)S.size()-2,0){
			auto &[du,dv,ddis]=srt[i];
			for(int x:{get<0>(srt[i+1]), get<1>(srt[i+1])}){
				i64 d0=dis(du, x), d1=dis(dv, x);
				if(d0<d1){
					swap(d0, d1);
					swap(du, dv);
				}
				if(d0>ddis){
					ddis=d0;
					dv=x;
				}
			}
		}

		vi V;
		rep(i,0,(int)S.size()-1){
			V.clear();
			if(i!=0){
				V.pb(get<0>(prt[i-1]));
				V.pb(get<1>(prt[i-1]));
			}
			if(i!=(int)S.size()-1){
				V.pb(get<0>(srt[i+1]));
				V.pb(get<1>(srt[i+1]));
			}
			for(int x:S[i]){
				if(Q[x].empty()){
					continue;
				}

				for(const auto &[y,id]:Q[x]){
					for(int z:V){
						chmax(ans[id], tree0::dis(y, z)+dep[x]+dep[z]);
					}
				}
			}
		}

		int psz=totsz;
		for(const auto &[v,w]:G[u]){
			if(!vis[v]){
				totsz=(sz[v]<sz[u]? sz[v]: psz-sz[u]);
				slv(v);
			}
		}
	}
	void clear(int n,int q){
		rep(i,1,n){
			G[i].clear(), Q[i].clear();
			vis[i]=0;
		}
		fill(ans+1, ans+q+1, 0);
	}
}

void solve(){
	cin>>n;
	rep(i,1,n-1){
		int u,v,w; cin>>u>>v>>w;
		tree0::link(u, v, w);
	}
	tree0::init();
	rep(i,1,n-1){
		int u,v,w; cin>>u>>v>>w;
		tree1::link(u, v, w);
	}
	int q; cin>>q;
	rep(i,1,q){
		int x,y; cin>>x>>y;
		tree1::Q[y].pb(x, i);
	}
	tree1::totsz=n;
	tree1::slv(1);
	
	rep(i,1,q){
		cout<< tree1::ans[i] <<'\n';
	}

	tree0::clear(n);
	tree1::clear(n, q);
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	int t=1;
	while(t--){
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 17488kb

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

5

result:

wrong answer 1st numbers differ - expected: '6', found: '5'