最长树链

[编程题]最长树链

热度指数：108 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

树链是指树里的一条路径。美团外卖的形象代言人袋鼠先生最近在研究一个特殊的最长树链问题。现在树中的每个点都有一个正整数值，他想在树中找出最长的树链，使得这条树链上所有对应点的值的最大公约数大于1。请求出这条树链的长度。

输入描述:

第1行：整数n（1 ≤ n ≤ 100000），表示点的个数。
第2~n行：每行两个整数x，y表示xy之间有边，数据保证给出的是一棵树。
第n+1行：n个整数，依次表示点1~n对应的权值（1 ≤ 权值 ≤ 1,000,000,000）。

输出描述:

满足最长路径的长度

示例1

输入

输出

算法知识视频讲解

C/C++

RomanMJ

没有AC，发上来讨论下：

想法比较简单

1.将这颗树按照图中邻接矩阵的形式进行保存；

2.从每一个顶点出发做深度优先遍历，并将遍历中的所有途径点的权值进行保存：

2.1若途径点的权值集合的最大公约数为 1则舍弃该路径；

2.2若途径点的权值集合的最大公约数不为 1，则寻找可达点进行递归，并将当前路径长度与最大值进行比较；

计算最大公约数用辗转相除法：

int gcd(int a, int b){
	if (b == 0)
	{
		return a;
	}
	return gcd(b, a % b);
}

判断途径点集合的最大公约数是否==1使用如下方法：

bool gcdForVecNot1(vector<int>vec){
	if (vec.size() < 2)
	{
		return true;
	}
	sort(vec.begin(), vec.end());
	int res = gcd(vec[0], vec[1]);
	if (res == 1)
	{
		return false;
	}
	for (int i = 2; i < vec.size();i++)
	{
		res = gcd(vec[i], res);
		if (res == 1)
		{
			return false;
		}
	}
	return true;
}

判断DFS可达点如下：

vector<int> TravelCanReach(vector<vector<int>> &vec,vector<int> &weight, int i){
	vector<int> res;
	for (int j = 0; j < weight.size();j++)
	{
		if (weight[j] > 0 && vec[i][j] > 0)
		{
			res.push_back(j);
		}
	}
	return res;
}

DFS如下：

void dfs(vector<vector<int>> &vec,vector<int> &weight, vector<int> &num,  int i){
	if (gcdForVecNot1(num))
	{
		if (num.size() > MaxL)
		{
			MaxL = num.size();
		}
		vector<int> tmp = TravelCanReach(vec, weight, i);
		if (!tmp.empty())
		{
			for (int j = 0; j < tmp.size();j++)
			{
				num.push_back(weight[tmp[j]]);
				int t = weight[tmp[j]];
				weight[tmp[j]] = 0;
				dfs(vec, weight, num, tmp[j]);
				num.pop_back();
				weight[tmp[j]] = t;
			}
		}
	}
}

最终只能过13.5%，用例太难写了，希望大家看到问题请指出，源代码如下：

#include "bits/stdc++.h"
using namespace std;
int MaxL;
int gcd(int a, int b){
	if (b == 0)
	{
		return a;
	}
	return gcd(b, a % b);
}

bool gcdForVecNot1(vector<int>vec){
	if (vec.size() < 2)
	{
		return true;
	}
	sort(vec.begin(), vec.end());
	int res = gcd(vec[0], vec[1]);
	if (res == 1)
	{
		return false;
	}
	for (int i = 2; i < vec.size();i++)
	{
		res = gcd(vec[i], res);
		if (res == 1)
		{
			return false;
		}
	}
	return true;
}

vector<int> TravelCanReach(vector<vector<int>> &vec,vector<int> &weight, int i){
	vector<int> res;
	for (int j = 0; j < weight.size();j++)
	{
		if (weight[j] > 0 && vec[i][j] > 0)
		{
			res.push_back(j);
		}
	}
	return res;
}

void dfs(vector<vector<int>> &vec,vector<int> &weight, vector<int> &num,  int i){
	if (gcdForVecNot1(num))
	{
		if (num.size() > MaxL)
		{
			MaxL = num.size();
		}
		vector<int> tmp = TravelCanReach(vec, weight, i);
		if (!tmp.empty())
		{
			for (int j = 0; j < tmp.size();j++)
			{
				num.push_back(weight[tmp[j]]);
				int t = weight[tmp[j]];
				weight[tmp[j]] = 0;
				dfs(vec, weight, num, tmp[j]);
				num.pop_back();
				weight[tmp[j]] = t;
			}
		}
	}
}

int main(){
	int n;
	while (cin >> n)
	{
		MaxL = 1;
		vector<vector<int>> vec(n, vector<int>(n, 0));
		for (int i = 0; i < n - 1; i++)
		{
			int a, b;
			cin >> a >> b;
			vec[a - 1][b - 1] = 1;
			vec[b - 1][a - 1] = 1;
		}
		vector<int> weight(n, 0);
		for (int i = 0; i < n; i++)
		{
			cin >> weight[i];
		}
		vector<int> num;
		for (int i = 0; i < n; i++)
		{
			num.push_back(weight[i]);
			int t = weight[i];
			weight[i] = 0;
			dfs(vec, weight, num, i);
			num.pop_back();
			weight[i] = t;
		}
		cout << MaxL << endl;
	}
	return 0;
}

发表于 2017-07-09 19:59:40 回复(0)

teitoku

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <iostream>
#include <cmath>
#include<cstdio>
#include<cstring>
#include <algorithm>
#include <cctype>
#include <utility>
#include <map>
#include <string>
#include <cstdlib>
#include <queue>
#include <numeric>
#include <vector>
#include<set>
#include <cctype>
using namespace std;
const int maxn = 100050;
int maxlen = 0;
int rd[maxn];
int a[maxn];
vector<int>v[maxn];
inline bool scan(int &ret) {
   char c; int sgn;
   if (c = getchar(), c == EOF) return 0; //EOF
   while (c != '-' && (c<'0' || c>'9')) c = getchar();
   sgn = (c == '-') ? -1 : 1;
   ret = (c == '-') ? 0 : (c - '0');
   while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
   ret *= sgn;
   return 1;
}
struct node {
   int x;
   int len;
   int gcd;
};
void bfs(int x, int len, int gcd)
{
   node n1, n2;
   queue<node>q;
   n1.x = x;
   n1.len = len;
   n1.gcd = gcd;
   q.push(n1);
   while (!q.empty())
   {
       node n1 = q.front();
       q.pop();
       int nx = n1.x;
       int nlen = n1.len;
       int ngcd = n1.gcd;

       maxlen = max(nlen, maxlen);
       for(int i=0;i<v[nx].size();i++)
       {
           int next = v[nx][i];
           int usegcd = __gcd(a[next], ngcd);
           if (usegcd == 1)
           {
               n2.gcd = a[next];
               n2.len = 1;
               n2.x = next;
               q.push(n2);
           }
           else
           {
               n2.gcd = usegcd;
               n2.len = 1+nlen;
               n2.x = next;
               q.push(n2);
           }
       }
   }
}/*
void dfs(int x, int len,int gcd)
{
   maxlen = max(len, maxlen);
   for (int i = 0; i < v[x].size(); i++)
   {
       int next = v[x][i];
       int usegcd = __gcd(a[next], gcd);
       if (usegcd ==1)
           dfs(next, 1, a[next]);
       else
           dfs(next, len+1, usegcd);
   }

}*/
int main()
{

   int n;
   scan(n);
   for (int i = 2; i <= n; i++)
   {
       int a, b;
       scan(a);
       scan(b);
       v[a].push_back(b);
       rd[b]++;
   }
   int go = 0;
   for (int i = 1; i <= n; i++)
   {
       if (rd[i] == 0)
           go = i;
       scan(a[i]);
   }

   bfs(go,1,a[go]);

   printf("%d", maxlen);
   return 0;
}