题意

一二题题解 ：传送门
百度之星复赛第三题题意 传送门
中文题意，自己看吧
比赛的时候看错了题意，一直没想出，赛后补题

思路

就是按照规律进行中序遍历，情况有点多所以你得分类讨论
先预处理出
每个节点的作为根节点的树的最小节点下标是多少
每个节点的作为根节点的树的节点数是多少
然后我们开始中序遍历
如果两边都有节点，找比当前节点小的最小节点的一边
如果两边的最小节点都比当前节点大那么找，节点数最小的一边遍历
如果只有一边节点，判断这一边的最小节点是否比当前节点小，是则先遍历

AC_code:

/* Algorithm: 中序遍历 Author: anthony1314 Creat Time: Time Complexity: */

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <stack>
#include <cmath>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#define line printf("---------------------------\n")
#define mem(a, b) memset(a, b, sizeof(a))
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 1e5+5;

void add(int &x, int y) {
	x = (x + y) % mod;
}
vector<int> node[maxn];
int tot;
bool ma[maxn];// 0为根节点 1不为根节点
int mr[maxn], ans[maxn], sz[maxn];//子树最小的节点 每个节点的标号 以该节点为根节点的树 的节点数
int dfs1(int root) {
	sz[root] = 1;
	int minroot = maxn+5;
	for(int i = 0; i < node[root].size(); i++) {
		int u = node[root][i];
		minroot = min(minroot, dfs1(u));
		sz[root] += sz[u];
	}
	mr[root] = minroot;
	return min(root, minroot);
}
void dfs2(int root) {
// cout<<node[root].size()<<endl;
	if(node[root].size() == 1 && min(node[root][0], mr[node[root][0]]) > root) {
		ans[root] = ++tot;
		dfs2(node[root][0]);
		return;
	} else if(node[root].size() == 2 && min(node[root][0], mr[node[root][0]]) > root
	          						 && min(node[root][1], mr[node[root][1]]) > root) {
		if(sz[node[root][0]] == sz[node[root][1]]) {
			if(min(node[root][0], mr[node[root][0]]) > min(node[root][1], mr[node[root][1]])) {
				dfs2(node[root][1]);
				ans[root] = ++tot;
				dfs2(node[root][0]);
			} else {
				dfs2(node[root][0]);
				ans[root] = ++tot;
				dfs2(node[root][1]);
			}
		} else if(sz[node[root][0]] > sz[node[root][1]]) {
			dfs2(node[root][1]);
			ans[root] = ++tot;
			dfs2(node[root][0]);
		} else {
			dfs2(node[root][0]);
			ans[root] = ++tot;
			dfs2(node[root][1]);
		}
		return;
	}
	for(int i = 0; i < node[root].size(); i++) {
		if(mr[root] == min(node[root][i], mr[node[root][i]])) {
			dfs2(node[root][i]);
		}
	}
	ans[root] = ++tot;
	for(int i = 0; i < node[root].size(); i++) {
		if(mr[root] != min(node[root][i], mr[node[root][i]])) {
			dfs2(node[root][i]);
		}
	}
}
ll slove(int n) {
	ll u = 233LL;
	ll ret = 0;
	for (ll i = 1; i <= n; i++) {
// cout<<ans[i]<<endl;
		ret = (ret + (((i ^ ans[i]) % mod) * u) % mod) % mod;
		u = (u * 233LL) % mod;
	}
	return ret;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t, n, u, v;
	cin>>t;
	while(t--) {
		tot = 0;
		cin>>n;
		for(int i = 0; i <= n; i++) node[i].clear(), ma[i] = 0, sz[i] = 0;//初始化
		for(int i = 1; i <= n; i++) {
			cin>>u>>v;
			if(u != 0)
				node[i].push_back(u);
			if(v != 0)
				node[i].push_back(v);
			ma[u] = 1;
			ma[v] = 1;
		}
		int root;
		for(int i = 1; i <= n; i++) {
			if(ma[i] == 0) {
				root = i;
				break;
			}
		}
		dfs1(root);//预处理 遍历出深度和最小节点
		dfs2(root);//中序遍历
		cout<<slove(n)<<endl;

	}
	return 0;
}