NC15537. Go For Travel
描述
输入描述
The first line contains an integer number T, the number of test cases.
For each test case :
The first line contains an integer n(1 ≤ n ≤ 105), the number of vertices.
The following n−1 lines, each contains two integers u,v(1 ≤ u,v ≤ n), which means there is an edge between u and v.
It is guaranteed that the graph is connected.
The next line contains an integer m(1 ≤ m ≤ 106), the number of years.
The following m lines, the ith line contains two integers xi(1 ≤ xi≤ n),ki(1 ≤ ki≤ 106), the index of the city she starts travel and the money she carries in the ith year.
输出描述
For each year print the answer.
示例1
输入:
1 6 1 2 1 3 2 4 2 5 3 6 2 2 2 2 4
输出:
3 4
C++(g++ 7.5.0) 解法, 执行用时: 31ms, 内存消耗: 3188K, 提交时间: 2022-10-15 11:18:33
#include<stdio.h>
#include<string.h>
#include<vector>
#define N 100005
using namespace std;
vector<int>vt[N];
int dis1[N]={0},dis2[N]={0},maxx=0;
int n;
int max(int x,int y);
int min(int x,int y);
int max(int x,int y){
return x>y?x:y;
}
int min(int x,int y){
return x<y?x:y;
}
void dfs(int start,int last){
for(int i=0;i<vt[start].size();i++){
if(vt[start][i]==last)continue;
dis1[vt[start][i]]=dis1[start]+1;
dfs(vt[start][i],start);
}
}
int main(){
void dfs(int start,int last);
int test;
scanf("%d",&test);
while(test--){
scanf("%d",&n);
for(int i=1;i<=n;i++){vt[i].clear();}
int city1,city2;
for(int i=1;i<n;i++){
scanf("%d%d",&city1,&city2);
vt[city1].push_back(city2);
vt[city2].push_back(city1);
}
dfs(2,2);
int a1;
for(int i=1;i<=n;i++){
if(maxx<dis1[i]){
maxx=dis1[i];
a1=i;
}
}
for(int i=1;i<=n;i++){dis1[i]=0;}
dfs(a1,a1);
maxx=0;
for(int i=1;i<=n;i++){
if(maxx<dis1[i]){
maxx=dis1[i];
a1=i;
}
}
for(int i=1;i<=n;i++){dis2[i]=dis1[i];dis1[i]=0;}
dfs(a1,a1);
int years;
scanf("%d",&years);
for(int i=0;i<years;i++){
int start,money;
scanf("%d%d",&start,&money);
maxx=max(dis1[start],dis2[start]);
if(money<=maxx){
printf("%d\n",money+1);
}
else{
printf("%d\n",min(n,maxx+(money-maxx)/2+1));
}
maxx=0;
}
}
}
C++14(g++5.4) 解法, 执行用时: 40ms, 内存消耗: 4452K, 提交时间: 2018-05-18 00:10:13
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
vector<int> a[maxn];
int n;
int dis[maxn];
int dep[maxn];
int m;
void dfs(int k,int fa,int d)
{
dep[k]=d;
dis[k]=max(dis[k],d);
for(int i=0;i<a[k].size();i++)
{
int v=a[k][i];
if(v==fa) continue;
dfs(v,k,d+1);
}
}
int main()
{
// ios::sync_with_stdio(false);
int t;
int p,q;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
a[i].clear();
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&p,&q);
a[p].push_back(q);
a[q].push_back(p);
}
memset(dis,0,sizeof(dis));
memset(dep,0,sizeof(dep));
dfs(1,0,0);
//cout<<1<<endl;
int st=1;
for(int i=1;i<=n;i++)
{
if(dep[i]>dep[st])
{
st=i;
}
}
//cout<<st<<endl;
dep[st]=0;
dfs(st,0,0);
st=1;
for(int i=1;i<=n;i++)
{
if(dep[i]>dep[st]) st=i;
}
dep[st]=0;
dfs(st,0,0);
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&p,&q);
//cout<<dis[p]<<endl;
if(dis[p]>=q)
{
printf("%d\n",q+1);
}
else
{
printf("%d\n",min(n,(q-dis[p])/2+1+dis[p]));
}
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 41ms, 内存消耗: 3600K, 提交时间: 2018-04-22 11:13:07
#include<stdio.h>
#include<string.h>
#include<vector>
#define N 100005
using namespace std;
vector<int>vt[N];
int dis1[N],dis2[N];
void dfs(int u,int fa)
{
for(int i=0;i<vt[u].size();i++)
{
int to=vt[u][i];
if(to==fa)continue;
dis1[to]=dis1[u]+1;
dfs(to,u);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)dis1[i]=dis2[i]=0,vt[i].clear();
for(int i=0;i<n-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
vt[u].push_back(v);
vt[v].push_back(u);
}
dfs(1,1);
int s1,s2,ma=-1;
for(int i=1;i<=n;i++)
if(ma<dis1[i])
ma=dis1[i],s1=i;
for(int i=1;i<=n;i++)dis1[i]=0;
dfs(s1,s1);
ma=-1;
for(int i=1;i<=n;i++)
if(ma<dis1[i])
ma=dis1[i],s2=i;
for(int i=1;i<=n;i++)dis2[i]=dis1[i],dis1[i]=0;
dfs(s2,s2);
int q;
scanf("%d",&q);
while(q--)
{
int u,k;
scanf("%d%d",&u,&k);
int dist=max(dis1[u],dis2[u]);
if(dist>=k)printf("%d\n",k+1);
else printf("%d\n",min(n,dist+(k-dist)/2+1));
}
}
}