题目大意

---

题目大意：

你有一颗树：树开始时候1号点是红色的
现在就是你有两次操作：
1 u 把u点涂成红色
2 u 询问离u点最近红点在哪里？

---

1. 数据范围是$n,m\in [1,1e5]$时间限制是$5s$
2. 如果直接查询我们是可以直接树形dp$O(n)$去查询，跟新是$O(1)$
3. 如果直接去维护每个点的答案是跟新就是$O(n)$查询是$O(1)$的？
4. 那么我们可以考虑去均摊两个复杂度$O(n\sqrt{m})$
5. 就是我们可以这样考虑，我们每次先把要修改的点先存起来不修改，等修改个数超过$\sqrt{m}$的时候我们再去修改
6. 首先我们对于询问我们要去查询这$\sqrt{m}$个点查询两点距离要LCA$\to log$那么复杂度是$(m-\sqrt{m})\ast log(n)$
7. 对于跟新我们直接跑一遍树形dp$O(n\ast \sqrt{m})$最多更新$\sqrt{m}$次
8. 总的复杂度是$O(max((m-\sqrt{m})\ast log(n),n\sqrt{m}))$
9. $cf机子很快$

---

AC code

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 500010;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);
}
int n, m;
vector<int> G[maxn];
int dp[maxn];
bool is[maxn];
int depth[maxn], fa[maxn][20];
inline void init(int u, int f) {depth[u] = depth[f] + 1;fa[u][0] = f;for(int i = 1; i < 19; ++ i) fa[u][i] = fa[fa[u][i-1]][i-1];for(auto it : G[u]) {if(it == f) continue;init(it,u);}
}inline int LCA(int u, int v) {if(depth[u] > depth[v]) swap(u,v);int delta = depth[v] - depth[u];for(int i = 19; i >= 0; -- i) if(delta >> i & 1) v = fa[v][i];if(u == v) return v;for(int i = 19; i >= 0; -- i) if(fa[u][i] != fa[v][i])u = fa[u][i], v = fa[v][i];return fa[u][0];
}inline void dfs(int u, int fa) {if(is[u]) dp[u] = 0;for(auto it : G[u]) {if(it == fa) continue;dfs(it,u);dp[u] = min(dp[it]+1,dp[u]);}
}inline void dfs1(int u, int fa) {dp[u] = min(dp[fa]+1,dp[u]);for(auto it : G[u]) {if(it == fa) continue;dfs1(it,u);}
}
vector<int> stk;
int main() {IOS;ms(dp,INF);is[1] = 1;stk.push_back(1);cin >> n >> m;for(int i = 2; i <= n; ++ i) {int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}init(1,0);int lim = sqrt(m);while(m --) {int op, u;cin >> op >> u;if(op == 1) stk.push_back(u);else {int ans = dp[u];for(auto it : stk) ans = min(ans,depth[u]+depth[it]-2*depth[LCA(u,it)]);cout << ans << endl;}if(stk.size() > lim) { // 单修改超过lim时候直接跟新for(auto it : stk) is[it] = 1;dfs(1,0);dfs1(1,0);stk.clear();}}return 0;
}