列表

详情

NC232165. Rain_w Loves Skirt

描述

There are n shops in the city where rain_w lives. And there are n-1 roads connecting these shops, any two shops can reach each other directly or indirectly through these n-1 roads. The length of the i-th road is w_i, connecting shops u_i and v_i.

As we all know, rain_w likes to wear skirts. There are m types of skirts, and each shop only sells one kind of skirt. More formally, the i-th shop only sells the k_i-th skirt.It is guaranteed that every type of skirt has at least one shop selling it.

Every skirt has its rarity, the x-th skirt is more rare than y-th skirt if and only if there are fewer shops selling skirt x than y. If the number of shops selling them is the same, then the skirt with the smaller id is more rare.

Every day, Rain_w will choose two types of skirts (x,y) which he wants to buy, (it is guaranteed that x is more rare than y). Then his mother would send him to a shop which sells x-th skirts as a starting point. After buying skirts in this starting point and putting them on, Rain_w will choose another shop that sells one of these of skirts (means sells x or y) and walk to it along the shortest path, and then he will go home in his mother's car. Because Rain_w enjoys the feeling of wearing a skirt, he will choose the shop with the longest distance that he needs to walk.

Rain_w' s mother knows rain_w' s thoughts, but she doesn't want the cute rain_w to walk outside for too long in a skirt. Therefore, she will carefully chooses the starting point to minimize the distance rain_w walks.

There are q days. Each day, you will know the two skirts rain_w choose, you need to write a program to help rain_w calculate how long he will walk with skirt that day with his mother's control.

输入描述

The first line contains two integers  --the number of shops in the city and the number of skirt types.

Then n-1 lines follow, the i-th line contains three integers  denoting i-th road which connecting two shops.

Then a line follows contains n integers, the i-th integer  denoting the i-th shop sells k_i-th  skirt.

Then follows an integer  -- the number of days

Then q line follow, the i-th line contain two integers , denoting the two types of skirts rain_w chose on the i-th day.

输出描述

Print q lines, the i-th line contains an integer denoting how long rain_w will walk with skirt on i-th day.

示例1

输入: 

8 3
1 2 1
2 3 1
3 4 1
4 5 1
3 6 1
6 7 1
7 8 1
1 2 1 2 1 2 1 3
2
2 1
3 2

输出: 

3
4

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 520ms, 内存消耗: 24740K, 提交时间: 2022-10-15 22:10:11 

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;
const ll INF=1e16;
const int N=5e4+5;
ll dis[N];int dpth[N];
int od[N];vector<int>ov[N];vector<ll>vl[N];
int dfn[N*2][20],dnl[N],dnr[N],tot;
int lg2[N*2];
int n,m,k;
vector<int>col[N];int D1[N],D2[N];
int bel[N];
#define pb push_back
#define x ov[p][i]
void dfs(int p){
	dfn[++tot][0]=p,dnl[p]=dnr[p]=tot;
	For(i,0,od[p]-1){
		if(dpth[x])continue;
		dis[x]=dis[p]+vl[p][i],dpth[x]=dpth[p]+1;
		dfs(x);
		dfn[++tot][0]=p,dnr[p]=tot;
	}
}
#define dmin(a,b) (dpth[a]<dpth[b]?a:b)
int lca(int p1,int p2){
	int l=min(dnl[p1],dnl[p2]);
	int r=max(dnr[p1],dnr[p2]);
	int lg=lg2[r-l+1]-1;
	r=max(l,r-(1<<lg)+1);
//	cerr<<l<<" "<<r<<" "<<lg<<"\n";
	return dmin(dfn[l][lg],dfn[r][lg]);
}
ll gdis(int p1,int p2){
	int a=lca(p1,p2);
	return dis[p1]+dis[p2]-dis[a]-dis[a];
}
map<int,ll>mp[N];
void prc(){
	int q;cin>>q;
	while(q--){
		int c1,c2;cin>>c1>>c2;
		if(col[c1].size()<col[c2].size()||(col[c1].size()==col[c2].size()&&c2>c1)) swap(c1,c2);
		if(mp[c1].count(c2)){cout<<mp[c1][c2]<<"\n";continue;}
		ll ans=INF;
		for(auto p:col[c2]){
			ans=min(ans,max({gdis(p,D1[c1]),gdis(p,D2[c1]),gdis(p,D1[c2]),gdis(p,D2[c2])}));
		}
		mp[c1][c2]=ans;
		cout<<ans<<"\n";
	}
}
void init(){
	dpth[1]=1,dfs(1);
	for(int i=1;i<=tot;i<<=1) lg2[i]++;
	For(i,1,tot) lg2[i]+=lg2[i-1];
	For(i,1,19){
		int len=(1<<(i-1));
		For(j,1,tot){
			int p2=min(tot,j+len);
			dfn[j][i]=dmin(dfn[j][i-1],dfn[p2][i-1]);
		}
	}
	For(i,1,n)if(gdis(1,i)>gdis(1,D1[bel[i]])) D1[bel[i]]=i;
	For(i,1,n)if(gdis(D1[bel[i]],i)>gdis(D2[bel[i]],D1[bel[i]])) D2[bel[i]]=i;
} 
void input(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>k;m=n-1;
	For(i,1,m){
		int p1,p2;ll v;cin>>p1>>p2>>v;
		++od[p1],ov[p1].pb(p2),vl[p1].pb(v);
		++od[p2],ov[p2].pb(p1),vl[p2].pb(v);
	}
	For(i,1,n)cin>>bel[i],col[bel[i]].pb(i),D1[bel[i]]=D2[bel[i]]=i;
}
signed main(){
//	freopen("in.txt","r",stdin);
	input();
	init();
	prc();
	return 0;
}

上一题

© 2024 nowcoder.com