結果

問題 No.364 門松木
コンテスト
ユーザー koyumeishi
提出日時 2016-03-16 02:04:52
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,285 bytes
コンパイル時間 915 ms
コンパイル使用メモリ 76,860 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-10-01 20:10:30
合計ジャッジ時間 6,984 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 2 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

//TLE
#include <iostream>
#include <vector>
#include <functional>
#include <bitset>
using namespace std;
template<typename V, typename H> void resize(vector<V>& vec, const H head){vec.resize(head);}
template<typename V, typename H, typename ... T> void resize(vector<V>& vec, const H& head, const T ... tail){
	vec.resize(head);
	for(auto& v: vec) resize(v, tail...);
}
//fill(vector, value); //v[x][y]...[z] = value;
template<typename V, typename T> void fill(V& vec_, const T& val){vec_ = val;};
template<typename V, typename T> void fill(vector<V>& vec, const T& val){
	for(auto& v: vec) fill(v, val);
}


class UnionFindTree{
	struct base_node{
		int parent;
		int rank;
		int size;
	};
	
	vector<base_node> node;
public:
	UnionFindTree(int n){
		node.resize(n);
		for(int i=0; i<n; i++){
			node[i].parent=i;
			node[i].rank=0;
			node[i].size=1;
		}
	}

	int find(int x){  //return root node of x
		if(node[x].parent == x) return x;
		else{
			return node[x].parent = find(node[x].parent);
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}

	int size(int at){
		return node[find(at)].size;
	}

	void unite(int x, int y){
		x = find(node[x].parent);
		y = find(node[y].parent);

		if(x==y) return;

		if(node[x].rank < node[y].rank){
			node[x].parent = y;
			node[y].size += node[x].size;
		}else if(node[x].rank > node[y].rank){
			node[y].parent = x;
			node[x].size += node[y].size;
		}else{
			node[x].rank++;
			unite(x,y);
		}
	}
};


bool is_kadomatsu_sequence(vector<int> x){
	if(x.size() != 3) return false;
	if(x[0] < x[1] && x[1] > x[2] && x[2] != x[0]) return true;
	if(x[0] > x[1] && x[1] < x[2] && x[2] != x[0]) return true;
	return false;
}

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	vector<vector<int>> G(n);
	vector<vector<int>> e(n);

	vector<int> u(n-1),v(n-1);

	for(int i=0; i<n-1; i++){
		cin >> u[i] >> v[i];
		u[i]--; v[i]--;
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);

		e[u[i]].push_back(i);
		e[v[i]].push_back(i);
	}

	int ans = 0;
	for(int edge=0; edge<(1<<(n-1)); edge++){
		UnionFindTree uft(n);
		for(int j=0; j<n-1; j++){
			if((edge>>j)&1) uft.unite(u[j], v[j]);
		}

		function<int(int,int,int,int)> dfs = [&](int pos, int last, int first, int second){
			if(first != -1 && second != -1){
				if(is_kadomatsu_sequence({a[first], a[second], a[pos]})) return 1;
				else return -10000;
			}
			int ret = 0;
			if(first != -1 && second == -1){
				for(int j=0; j<G[pos].size(); j++){
					if(G[pos][j] == last || !uft.same(pos, G[pos][j]) ) continue;
					//if(a[pos] == a[G[pos][j]] || a[first]==a[G[pos][j]]) continue;
					ret += dfs(G[pos][j], pos, first, pos);
				}
			}else{
				for(int j=0; j<G[pos].size(); j++){
					if(G[pos][j] == last || !uft.same(pos, G[pos][j]) ) continue;
					//if(a[pos] == a[G[pos][j]]) continue;
					ret += dfs(G[pos][j], pos, pos, second);
				}
			}
			return ret;
		};

		vector<int> cnt(n, 0);
		for(int i=0; i<n; i++){
			cnt[uft.find(i)] += dfs(i, -1, -1,-1);
			//cerr << i << " " << dfs(i, -1,-1,-1) << endl;
		}
		for(int i=0; i<n; i++){
			if(cnt[uft.find(i)] > 0){
				//ans = max(ans, uft.size(i));
				ans = max(ans, cnt[uft.find(i)]/2);
			}
		}
	}

	
	//if(ans <= 2) ans = 0;

	cout << ans << endl;


	return 0;
}
0