提供一种轻重链剖分+dp的做法
先把2树的lca预处理好,用下面这个方式查询可以省去上跳的时间(直接欧拉序也行,不过比赛的时候能想到欧拉序我就不会写dp了QAQ):
int lca(int u, int v) { if (d[u] > d[v])swap(u, v);//默认v的深度较大 while (d[v] > d[u]) v = f[lg[d[v] - d[u]] - 1][v];//上跳2^(lg(深度差)-1步) if (u == v)return v; else return -1; }
然后把1树重链预处理出来,每次首先沿着重链跑滑动窗口,暴力pop与新加入节点冲突的祖先节点。这样得到的答案能尽可能大,之后加上最优化剪支就可以不用搜索很多比较小的子树。
#include<bits/stdc++.h> using namespace std; #define ll long long #define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL) #define pii pair<int,int> #define pll pair<ll,ll> const double PI = acos(-1); const int inf = 2e9; const ll lnf = 1e18 + 7; const int maxn = 3e5 + 5; const int N = 1 << 30 - 1; ll mod = 998244353; double eps = 1e-6; int head[maxn], f[22][maxn], edge_cnt = 0, d[maxn]; int lg[maxn]; int S; struct edge { int to, next; }e[2 * maxn]; void add(int from, int to) { e[++edge_cnt].to = to; e[edge_cnt].next = head[from]; head[from] = edge_cnt; } void lg_init(int n) { for (int i = 1; i <= n; i++) { lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);//1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5(打表) //cout << lg[i] << " "; } }//lg(i)数组实际意义:到根至多要跳lg(i)步;eg:lg(8)=4,8=2^3=1+2+4+1 void pre_lca(int from) { //cout << from << endl; for (int i = 1; (1 << i) <= d[from]; i++) f[i][from] = f[i - 1][f[i - 1][from]]; for (int i = head[from]; i; i = e[i].next) { int to = e[i].to; //cout << to << endl; if (to == f[0][from])continue; d[to] = d[from] + 1;//处理深度 f[0][to] = from;//标记父节点 pre_lca(to); } } int lca(int u, int v) { if (d[u] > d[v])swap(u, v);//默认v的深度较大 while (d[v] > d[u]) v = f[lg[d[v] - d[u]] - 1][v];//上跳2^(lg(深度差)-1步) if (u == v)return v; else return -1; } vector<int>G[maxn]; vector<int>inq; int ddfmax[maxn], ddf[maxn], siz[maxn], son[maxn]; int predfs(int now, int fa) { siz[now] = 1; int maxson = -1; ddfmax[now] = ddf[now]; int to; for (int i=0;i<G[now].size();i++) { to = G[now][i]; if (to == fa)continue; ddf[to] = ddf[now] + 1; ddfmax[now] = max(ddfmax[now], predfs(to, now)); siz[now] += siz[to]; if (siz[to] > maxson) son[now] = to, maxson = siz[to]; } return ddfmax[now]; } int ans = 1; pii getans(int from,int last) { int sz = inq.size(); int res = 1; int p = last; for (int i = sz - 2; i >= last; i--) { if (lca(inq[i], from) == -1) res++; else { p = i + 1; break; } } /*if (res != 1) for (int i = p; i < sz; i++) cout << inq[i] << " "; cout << endl;*/ ans = max(res, ans); return make_pair(p, sz - p); } void dfs(int from, int fa, int last) { inq.push_back(from); pii tmp = getans(from, last); if (!son[from]) { inq.pop_back(); return; } dfs(son[from], from, tmp.first); for (auto to : G[from]) { if (to == fa || to == son[from])continue; if(ddfmax[from] - ddf[from]+ tmp.second > ans) dfs(to, from, tmp.first); } inq.pop_back(); } int main() { /* 3 5 2 1 2 5 5 3 2 4 2 1 1 5 1 3 3 4 5 5 3 3 1 5 4 3 2 5 3 5 1 3 4 3 2 */ //fastio; lg_init(3e5); S = 1; int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); //init edge_cnt = 0; ans = 1; while (inq.size() > 0) inq.pop_back(); for (int i = 1; i <= n; i++) son[i] = 0, head[i] = -1, G[i].clear(); int x, y; for (int i = 1; i < n; ++i) { scanf("%d %d", &x, &y); G[x].push_back(y); G[y].push_back(x); } for (int i = 1; i < n; ++i) { scanf("%d %d", &x, &y); add(x, y); add(y, x); } //preprocess d[1] = 0; f[0][S] = S; pre_lca(1); ddf[1] = 0; predfs(1, -1); //getans for (auto i : G[1]) dfs(i, 1, 0); printf("%d\n", ans); } return 0; }