rt,我在打出这道题之后第一次提交是27pts,后来放大了几个无关紧要的数据后逐渐上升到37pts,然后是46pts
一开始怀疑是求距离的时候LCA出现问题了,于是直接贴了LCA板题里的LCA,没想到分数竟然还能降低,后来想到是不是数据有奇怪的放大,因为倍增,理论上应该不会因为数据太小而WA,结果确实没有对pts有增长
现在是实在看不出来问题出在哪里了,希望有dl能够解答一下
下面是代码(同时放了46pts和37pts的两份,数据范围不用在意,37pts版与前者相比只有init和LCA函数有一些区别)
//46pts
#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#define ll long long
#define reg register int
#define gc getchar()
#define MAXN 200
#define MOD
using namespace std;
inline ll read( void ) ;
int n,u_,v_;
vector<int> T[MAXN];
int d[MAXN],anc[MAXN][50],w[MAXN];
int dpt,wid;
inline void link( int u , int v ){
T[u].push_back(v);
T[v].push_back(u);
}
inline void dfs( int nd , int fa ){
for( reg i = 0 ; i < T[nd].size() ; i++ ){
int to = T[nd][i];
if( to == fa ) continue;
//跳过父节点
d[to] = d[nd] + 1 ;
dpt = max( dpt , d[to] ) ;
w[ d[to] ]++;
//这个深度的数字数量+1
wid = max( wid , w[ d[to] ] );
//分别维护一下wid和dpt的最大值
anc[to][0] = nd ;
dfs(to,nd);
}
}
inline void init( void ){
for( reg i = 1 ; i <= 19 ; i++ ){
for( reg j = 1 ; j <= n ; j++ ){
anc[j][i] = anc[ anc[j][i-1] ][i-1] ;
}
}
}
inline int LCA( int x , int y ){
if( d[x] < d[y] ) swap(x,y);
//保证d[x]更大
for( reg i = 19 ; i >= 0 ; i-- )
if( d[ anc[x][i] ] >= d[y] ) x = anc[x][i];
if( x == y ) return x ;
for( reg i = 19 ; i >= 0 ; i-- )
if( anc[x][i] != anc[y][i] )
x = anc[x][i] , y = anc[y][i] ;
return anc[x][0];
}
inline void dis( int u , int v ){
int lca = LCA( u,v );
int ans = d[u] * 2 + d[v] - d[lca] * 3 ;
printf("%d\n",ans);
}
int main( void ) {
n = read();
for( reg i = 1 ; i < n ; i++ ){
u_ = read();
v_ = read();
link(u_,v_);
}
u_ = read();
v_ = read();
init();
d[1] = 1 ;
w[1] = 1 ;
dfs(1,-1);
printf("%d\n",dpt);
printf("%d\n",wid);
dis(u_,v_);
/*test
for( reg i = 1 ; i <= n ; i++ )
if( w[i] ) printf("%d ",w[i]);
else break;
//*/
return 0;
}
inline ll read( void ) {
ll x = 0 , f = 0 ;
char ch = gc ;
while( !isdigit( ch ) )
f |= ( ch == '-' ) , ch = gc ;
while( isdigit( ch ) )
x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ) , ch = gc ;
return f ? -x : x ;
}
//37pts
#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#define ll long long
#define reg register int
#define gc getchar()
#define MAXN 200
#define MOD
using namespace std;
inline ll read( void ) ;
int n,u_,v_;
vector<int> T[MAXN];
int d[MAXN],anc[MAXN][50],w[MAXN];
int dpt,wid;
inline void link( int u , int v ){
T[u].push_back(v);
T[v].push_back(u);
}
inline void dfs( int nd , int fa ){
for( reg i = 0 ; i < T[nd].size() ; i++ ){
int to = T[nd][i];
if( to == fa ) continue;
//跳过父节点
d[to] = d[nd] + 1 ;
dpt = max( dpt , d[to] ) ;
w[ d[to] ]++;
//这个深度的数字数量+1
wid = max( wid , w[ d[to] ] );
//分别维护一下wid和dpt的最大值
anc[to][0] = nd ;
dfs(to,nd);
}
}
inline void init( void ){
for( reg i = 1 ; i <= 49; i++ ){
for( reg j = 1 ; j <= n ; j++ ){
anc[j][i] = anc[ anc[j][i-1] ][i-1];
}
}
}
inline int LCA( int x , int y ){
if( d[x] > d[y] ) swap(x,y);
//保证d[y]是更大的,我们需要将y不断向上推
for( reg i = 49 ; i >= 0 ; i-- )
if( d[anc[y][i]] >= d[x] ) y = anc[y][i];
if( y == x ) return x;
for( reg i = 49 ; i >= 0 ; i-- ){
if( anc[x][i] != anc[y][i] )
x = anc[x][i] , y = anc[y][i] ;
}
return anc[x][0];
}
inline void dis( int u , int v ){
int lca = LCA( u,v );
int ans = d[u] * 2 + d[v] - d[lca] * 3 ;
printf("%d\n",ans);
}
int main( void ) {
n = read();
for( reg i = 1 ; i < n ; i++ ){
u_ = read();
v_ = read();
link(u_,v_);
}
u_ = read();
v_ = read();
init();
d[1] = 1 ;
w[1] = 1 ;
dfs(1,-1);
printf("%d\n",dpt);
printf("%d\n",wid);
dis(u_,v_);
/*test
for( reg i = 1 ; i <= n ; i++ )
if( w[i] ) printf("%d ",w[i]);
else break;
//*/
return 0;
}
inline ll read( void ) {
ll x = 0 , f = 0 ;
char ch = gc ;
while( !isdigit( ch ) )
f |= ( ch == '-' ) , ch = gc ;
while( isdigit( ch ) )
x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ) , ch = gc ;
return f ? -x : x ;
}