QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#764026	#9570. Binary Tree	Lynia	RE	0ms	3612kb	C++23	6.1kb	2024-11-19 23:25:39	2024-11-19 23:25:39

Judging History

你现在查看的是最新测评结果

[2024-11-19 23:25:39]
评测

测评结果：RE
用时：0ms
内存：3612kb

查看

[2024-11-19 23:25:39]
提交

answer

///////////        
//                   //      //
//              ////////////////////
//                   //      //
//                 
///////////

//          
//          
//           //     //    ////////     /\     /////////
//           //     //   //      //          //       //
//            ////////   //      //    //    //       //
//                  //   //      //    //    //       //
//////////   ////////    //      //    //     /////////////

//#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
#include <optional>
//#include <Windows.h>

using namespace std;

#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define all1(i) i.begin() + 1,i.end()
#define endl '\n'
#define px first
#define py second

using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
	out << '(' << p.first << ", " << p.second << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
	for (T i : ve)
		out << i << ' ';
	return out;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
	for (auto i : mp)
		out << i << '\n';
	return out;
}

template<typename ...T>
bool _debug(T... a) {
	((cout << a << ' '), ...);
	cout << endl;
	return -1;
}

const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };

//#include "Lynia.h"
namespace MyTools
{
	template <typename T>
	class Math;

	template <const int T>
	class ModInt;
}

namespace MT = MyTools;
using Math = MT::Math<ll>;
#define geo MT::Geo

const int mod = 1e9 + 7;
using mint = MT::ModInt<mod>;

const int N = 1e6 + 10;

int ask(int x, int y) {
	cout << "? " << x << ' ' << y << endl;
	cout.flush();
	int res; cin >> res;
	return res;
}

void answer(int x) {
	cout << "! " << x << endl;
	cout.flush();
	return;
}

void solve(int CASE)
{
	int n; cin >> n;
	var g = vector<vector<int>>(n + 1, vector<int>());
	fa(i, 1, n) {
		int x, y; cin >> x >> y;
		if (x)g[i].pb(x), g[x].pb(i);
		if (y)g[i].pb(y), g[y].pb(i);
	}

	// 获取重心
	int root = 0;                   // 重心
	int now_n = n;                  // 当前子树的大小，因为重心一直会变，原重心会被删，所以得加上这个
	var siz = vector<int>(n + 1);   // i 的每个子树的大小
	var mxsiz = vector<int>(n + 1); // i 的每个子树的大小的最大值
	var vis = vector<bool>(n + 1);  // 存哪些点已经当过重心用了
	mxsiz[0] = IINF;                // 找重心用

	// 找重心
	var getroot = [&](var getroot, int now, int fa)->void {
		// 每次遍历整个树的时候都不用刷新 siz/mxsiz 数组，因为每次都会更新
		siz[now] = 1; mxsiz[now] = 0;

		for (var& to : g[now]) {
			if (to == fa or vis[to])continue;
			getroot(getroot, to, now);
			siz[now] += siz[to];                   // 计算 now 作为子树的大小
			mxsiz[now] = max(mxsiz[now], siz[to]); // 找 now 的每个子树大小的最大值
		}

		// 所有子树，包括父节点的
		mxsiz[now] = max(mxsiz[now], now_n - siz[now]);
		
		// 看看当前是不是重心
		// 要满足 now 的最大子树的大小不能超过 root 的最大子树的大小
		if (mxsiz[now] < mxsiz[root])root = now;
		};

	var dfs = [&](var dfs, int now)->void { // now 为当前重心
		vis[now] = 1;
		var son = vector<int>();
		for (var& to : g[now]) {
			if (vis[to])continue;
			son.pb(to);
		}
		// 查询重心的度
		if (son.size() == 0)answer(now); // 本身就是答案
		else if (son.size() == 1) {      // 只有两个点
			int res = ask(son[0], now);
			if (res == 0)answer(son[0]);
			else answer(now);
		}
		else if (son.size() == 2) {      // 直接问两个子树
			int res = ask(son[0], son[1]);
			if (res == 0) {
				root = 0;
				mxsiz[0] = IINF;
				now_n = siz[son[0]];
				getroot(getroot, son[0], now);
				getroot(getroot, root, 0);

				dfs(dfs, root);
			}
			else if (res == 2) {
				root = 0;
				mxsiz[0] = IINF;
				now_n = siz[son[1]];
				getroot(getroot, son[1], now);
				getroot(getroot, root, 0);

				dfs(dfs, root);
			}
			else answer(now);
		}
		else { // 问两个大小较大的子树，因为在中间的自然会多一个节点
			sort(all(son), [&](int x, int y)->bool {
				return siz[x] > siz[y];
				});
			int res = ask(son[0], son[1]);
			if (res == 0) {
				root = 0;
				mxsiz[0] = IINF;
				now_n = siz[son[0]];
				getroot(getroot, son[0], now);
				getroot(getroot, root, 0);

				dfs(dfs, root);
			}
			else if (res == 2) {
				root = 0;
				mxsiz[0] = IINF;
				now_n = siz[son[1]];
				getroot(getroot, son[1], now);
				getroot(getroot, root, 0);

				dfs(dfs, root);
			}
			else {
				vis[now] = 0;
				vis[son[0]] = vis[son[1]] = 1;
				root = 0;
				mxsiz[0] = IINF;
				now_n = siz[now];
				getroot(getroot, now, 0);
				getroot(getroot, root, 0);
				dfs(dfs, root);
			}
		}
		};

	getroot(getroot, 1, 0);
	getroot(getroot, root, 0);

	dfs(dfs, root);

	return;
}

int main()
{
	//SetConsoleOutputCP(CP_UTF8);
	//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	fa(i, 1, _)solve(i);
	return 0;
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3612kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: