咸阳做网站公司,安平县护栏网站建设,可以看国外网站的dns,做网站有哪些要求枚举中点x( 即选出的三个点 a , b , c 满足 dist( x , a ) dist( x , b ) dist( x , c ) ) , 然后以 x 为 root 做 dfs , 显然两个位于 x 的同一颗子树内的点是不可能被同时选到的 . 我们对 x 的每一颗子树进行 dfs , 记录下当前子树中的点到 x 距离为 d ( 1 d n )…枚举中点x( 即选出的三个点 a , b , c 满足 dist( x , a ) dist( x , b ) dist( x , c ) ) , 然后以 x 为 root 做 dfs , 显然两个位于 x 的同一颗子树内的点是不可能被同时选到的 . 我们对 x 的每一颗子树进行 dfs , 记录下当前子树中的点到 x 距离为 d ( 1 d n ) 有多少个 , 记为 cnt[ 0 ][ i ] . 然后 cnt[ 1 ][ i ] 记录之前 dfs 过的子树的 cnt[ 0 ][ i ] 之和 , cnt[ 2 ][ i ] 记录之前 dfs 过的子树中任意两颗不同子树中的cnt[ 0 ][ i ] * cnt[ 0 ][ i ] 之和 . cnt[ ][ i ] 的计算看代码----------------------------------------------------------------------------#includecstdio#includecstdlib#includecstring#includealgorithm#includeiostream#define clr( x , c ) memset( x , c , sizeof( x ) )#define rep( i , n ) for( int i 0 ; i n ; i )#define REP( x ) for( edge* e head[ x ] ; e ; e e - next )using namespace std;typedef long long ll;const int maxn 5000 5;ll cnt[ 3 ][ maxn ];int n;struct edge {int to;edge* next;} E[ maxn 1 ] , *pt E , *head[ maxn ];inline void add_edge( int u , int v ) {pt - to v;pt - next head[ u ];head[ u ] pt;pt - to u;pt - next head[ v ];head[ v ] pt;}int dfs( int x , int fa , int d ) {cnt[ 0 ][ d ];REP( x ) if( e - to ! fa ) dfs( e - to , x , d );}void work() {ll ans 0;rep( i , n ) {clr( cnt[ 1 ] , 0 );clr( cnt[ 2 ] , 0 );REP( i ) {clr( cnt[ 0 ] , 0 );dfs( e - to , i , 1 );rep( i , n ) {ans cnt[ 0 ][ i ] * cnt[ 2 ][ i ];cnt[ 2 ][ i ] cnt[ 0 ][ i ] * cnt[ 1 ][ i ];cnt[ 1 ][ i ] cnt[ 0 ][ i ];}}}printf( %lld\n , ans );}void init() {clr( head , 0 );cin n;rep( i , n - 1 ) {int u , v , d;scanf( %d%d , u , v );add_edge( --u , --v );}}int main() {freopen( test.in , r , stdin );init();work(); return 0; } ---------------------------------------------------------------------------- 3522: [Poi2014]HotelTime Limit: 20 Sec Memory Limit: 128 MBSubmit: 273 Solved: 132[Submit][Status][Discuss]Description有一个树形结构的宾馆n个房间n-1条无向边每条边的长度相同任意两个房间可以相互到达。吉丽要给他的三个妹子各开一个房间。三个妹子住的房间要互不相同否则要打起来了为了让吉丽满意你需要让三个房间两两距离相同。有多少种方案能让吉丽满意Input第一行一个数n。接下来n-1行每行两个数x,y表示x和y之间有一条边相连。Output让吉丽满意的方案数。Sample Input7 1 2 5 7 2 5 2 3 5 6 4 5Sample Output5HINT【样例解释】{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}【数据范围】n≤5000SourceBy Dzy 转载于:https://www.cnblogs.com/JSZX11556/p/4643812.html
