网站建设大约需要多少钱,赣州优化,免费设计logo图标生成器,软件公司是干嘛的正题
题目链接:https://www.luogu.com.cn/problem/P2056 题目大意 nnn个点的一棵树#xff0c;开始全是黑点#xff0c;有操作
取反一个点的颜色求最远的黑点之间的距离 解题思路
根据点分治每个点和分散开来的重心连边#xff0c;然后每个点往上只会有logloglog层节点。…正题
题目链接:https://www.luogu.com.cn/problem/P2056 题目大意
nnn个点的一棵树开始全是黑点有操作
取反一个点的颜色求最远的黑点之间的距离 解题思路
根据点分治每个点和分散开来的重心连边然后每个点往上只会有logloglog层节点。
对于每个点分树上节点我们需要维护最长路和次长路然后要注意它们不能在同一个点分子树上。
只会对于每个点xxx我们需要维护xxx的点分树子树中每个点到xxx的父节点的真实距离的堆。然后还有每个点的所有子节点的堆顶元素的堆。还有一个维护每个节点答案的堆。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecctype
#includequeue
#includeset
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N1e510,inf1e9,T18;
struct node{int to,next;
}a[N*2];
int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
int n,tot,num,root,q,ls[N],f[N],siz[N],d[N],fa[N];
int dep[N],g[N][T1];bool v[N],vis[N];
struct heap{priority_queueint q1,q2;void insert(int x){q1.push(x);}void erase(int x){q2.push(x);}int top(){while(!q2.empty()q1.top()q2.top())q2.pop(),q1.pop();return q1.top();}int top2(){int wtop();erase(w);int anstop();insert(w);return ans;}int size(){return q1.size()-q2.size();}
}q1[N],q2[N],ans;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa){dep[x]dep[fa]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;g[y][0]x;dfs(y,x);}return;
}
int LCA(int x,int y){if(dep[x]dep[y])swap(x,y);for(int iT;i0;i--)if(dep[g[y][i]]dep[x])yg[y][i];if(xy)return x;for(int iT;i0;i--)if(g[x][i]!g[y][i])xg[x][i],yg[y][i];return g[x][0];
}
int Dis(int x,int y)
{return dep[x]dep[y]-dep[LCA(x,y)]*2;}
void groot(int x,int fa){siz[x]1;f[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||vis[y])continue;groot(y,x);siz[x]siz[y];f[x]max(f[x],siz[y]);}f[x]max(f[x],num-siz[x]);if(f[x]f[root])rootx;return;
}
void calc(int x,int fa,int sav,int root){int disDis(root,x);q1[sav].insert(dis);for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||vis[y])continue;calc(y,x,sav,root);}return;
}
int count(int x)
{return q2[x].top()q2[x].top2();}
void build(int x){vis[x]1;q2[x].insert(0);int Snum;for(int ils[x];i;ia[i].next){int ya[i].to;if(vis[y])continue;root0;num(siz[y]siz[x])?siz[y]:S-siz[x];groot(y,x);yroot;fa[y]x;calc(y,x,y,x);q2[x].insert(q1[y].top());build(y);}if(q2[x].size()1)ans.insert(count(x));return;
}
int main()
{nread();for(int i1;in;i){int xread(),yread();addl(x,y);addl(y,x);}//读入dfs(1,1);for(int j1;jT;j)for(int i1;in;i)g[i][j]g[g[i][j-1]][j-1];//预处理求LCA f[0]inf;numn;groot(1,1);build(root);numn;memset(v,0,sizeof(v));scanf(%d,q);while(q--){char op[3];int x;scanf(%s,op);if(op[0]C){xread();if(!v[x]){v[x]1;num--;if(q2[x].size()1)ans.erase(count(x));q2[x].erase(0);if(q2[x].size()1)ans.insert(count(x));for(int yx;fa[y];yfa[y]){if(q2[fa[y]].size()1)ans.erase(count(fa[y]));q2[fa[y]].erase(q1[y].top());q1[y].erase(Dis(x,fa[y]));if(q1[y].size())q2[fa[y]].insert(q1[y].top());if(q2[fa[y]].size()1)ans.insert(count(fa[y]));}}else{v[x]0;num;if(q2[x].size()1)ans.erase(count(x));q2[x].insert(0);if(q2[x].size()1)ans.insert(count(x));for(int yx;fa[y];yfa[y]){if(q2[fa[y]].size()1)ans.erase(count(fa[y]));if(q1[y].size())q2[fa[y]].erase(q1[y].top());q1[y].insert(Dis(x,fa[y]));q2[fa[y]].insert(q1[y].top());if(q2[fa[y]].size()1)ans.insert(count(fa[y]));}}}if(op[0]G){if(num1)printf(%d\n,num-1);else printf(%d\n,ans.top());}}return 0;
}
