Submission #76277653

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5,mod=998244353;

bool st;
int n,q,dfn[N],fa[N][17],id[N],dep[N],tot,siz[N],son[N],col[N];
vector<int> g[N];
struct sgt{int u,v,dis;}seg[N<<2];
inline void dfs1(int u,int last) {
	fa[u][0]=last;dep[u]=dep[last]+1;int maxn=0;siz[u]=1;
	for(int i=1;i<=16;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=0;i<g[u].size();i++) {
		int v=g[u][i];
		if(v==last) continue;
		dfs1(v,u);
		if(maxn<siz[v]) son[u]=v,maxn=siz[v];
		siz[u]+=siz[v];
	}
}
inline void dfs2(int u) {
	dfn[u]=++tot;id[tot]=u;
	if(son[u]) dfs2(son[u]);
	for(int i=0;i<g[u].size();i++) {
		int v=g[u][i];
		if(v==fa[u][0]||v==son[u]) continue;
		dfs2(v);
	}
}
inline int lca(int u,int v) {
	if(u==v) return u;
	if(dep[u]!=dep[v]) {
		if(dep[u]<dep[v]) swap(u,v);
		for(int i=16;i>=0;i--) {
			if(dep[fa[u][i]]>dep[v]) u=fa[u][i];
		}u=fa[u][0];
	}
	if(u==v) return u;
	for(int i=16;i>=0;i--) {
		if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	}return fa[u][0];
}
inline void push_up(int rt) {
	if(seg[rt<<1].dis==-1) {seg[rt]=seg[rt<<1|1];return;}
	if(seg[rt<<1|1].dis==-1) {seg[rt]=seg[rt<<1];return;}
	int u=seg[rt<<1].u,v=seg[rt<<1].v;
	int uu=seg[rt<<1|1].u,vv=seg[rt<<1|1].v;
	if(seg[rt<<1].dis>seg[rt<<1|1].dis) seg[rt]=seg[rt<<1];
	else seg[rt]=seg[rt<<1|1];
	if(-dep[lca(u,vv)]*2+dep[u]+dep[vv]>seg[rt].dis) seg[rt]={u,vv,-dep[lca(u,vv)]*2+dep[u]+dep[vv]};
	if(-dep[lca(u,uu)]*2+dep[u]+dep[uu]>seg[rt].dis) seg[rt]={u,uu,-dep[lca(u,uu)]*2+dep[u]+dep[uu]};
	if(-dep[lca(uu,v)]*2+dep[uu]+dep[v]>seg[rt].dis) seg[rt]={uu,v,-dep[lca(uu,v)]*2+dep[uu]+dep[v]};
	if(-dep[lca(v,vv)]*2+dep[v]+dep[vv]>seg[rt].dis) seg[rt]={v,vv,-dep[lca(v,vv)]*2+dep[v]+dep[vv]};
}
inline void build(int rt,int l,int r) {
	if(l==r) {seg[rt]={id[l],id[l],0};return;}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
	push_up(rt);
}
inline void modify(int rt,int l,int r,int pos,sgt x){
	if(l==r) {seg[rt]=x;return;}
	int mid=(l+r)>>1;
	if(pos<=mid) modify(rt<<1,l,mid,pos,x);
	else modify(rt<<1|1,mid+1,r,pos,x);
	push_up(rt);
}
bool ed;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cerr<<(double)(&st-&ed)/1024/1024<<'\n';
	cin>>n;
	for(int i=1;i<=n;i++) col[i]=1;
	for(int i=1;i<n;i++) {
		int u,v;cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}dfs1(1,0);dfs2(1);build(1,1,n);
	cin>>q;
	for(int i=1;i<=q;i++) {
		int x;cin>>x;
		if(col[x]) {col[x]=0;modify(1,1,n,dfn[x],{0,0,-1});}
		else {col[x]=1,modify(1,1,n,dfn[x],{x,x,0});}
		cout<<seg[1].dis<<'\n';
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'void dfs1(int, int)':
./Main.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         for(int i=0;i<g[u].size();i++) {
      |                     ~^~~~~~~~~~~~
./Main.cpp: In function 'void dfs2(int)':
./Main.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i=0;i<g[u].size();i++) {
      |                     ~^~~~~~~~~~~~

Judge Result