首页 > 代码库 > [xyz模拟题]动态维护树的直径
[xyz模拟题]动态维护树的直径
专出神题的xyz。
支持删加边、修改点权、维护树的直径。
LCT 需要额外记录子树信息。用一个堆维护。
#include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<vector> #include<queue> using namespace std; #define rep(i,x,y) for(i=x;i<=y;i++) #define _rep(i,x,y) for(i=x;i>=y;i--) #define REP(i,x,y) for(int i=(x);i<=(y);i++) #define ALL(x,S) for(x=S.begin();x!=S.end();x++) #define mp make_pair #define fi first #define se second #define pb push_back template<class T> inline void read(T&x){bool fu=0;char c;for(c=getchar();c<=32;c=getchar());if(c==‘-‘)fu=1,c=getchar();for(x=0;c>32;c=getchar())x=x*10+c-‘0‘;if(fu)x=-x;}; template<class T> inline void read(T&x,T&y){read(x);read(y);} template<class T> inline void read(T&x,T&y,T&z){read(x);read(y);read(z);} inline char getc(){char c;for(c=getchar();c<=32;c=getchar());return c;} typedef long long ll; typedef pair<int,int> pii; int max(int a,int b,int c){return max(max(a,b),c);} const int N=100010; const int inf=int(1e9); int n,m,i,j,k,x,y,u,v,w0,w1; multiset<int> son[N],AN; multiset<int>::iterator pos; priority_queue<pii> Q; int ch[N][2],fa[N],key[N];bool rev[N]; int lw[N],rw[N],ans[N],len[N]; void Hins(int i,int t){son[i].insert(lw[t]);} void Hdel(int i,int t){son[i].erase(son[i].find(lw[t]));} int mson(int i){return son[i].empty()?0:*son[i].rbegin();} int tson(int i){if(son[i].size()<=1)return mson(i);pos=--son[i].end();return *pos+*(--pos);} bool tp(int i){return !(ch[fa[i]][0]==i||ch[fa[i]][1]==i);} void REV(int i){if(i){rev[i]=!rev[i];swap(ch[i][0],ch[i][1]);swap(lw[i],rw[i]);}} void D(int i){if(rev[i])rev[i]=0,REV(ch[i][0]),REV(ch[i][1]);} void U(int i) { #define L ch[i][0] #define R ch[i][1] len[i]=len[L]+key[i]+len[R]; ans[i]=max(rw[L]+lw[R],max(rw[L],lw[R])+mson(i),tson(i))+key[i]; lw[i]=max(lw[L],len[L]+key[i]+mson(i),len[L]+key[i]+lw[R]); rw[i]=max(rw[R],len[R]+key[i]+mson(i),len[R]+key[i]+rw[L]); Q.push(mp(ans[i],i)); } void rot(int i,int t){int x,y;x=ch[i][!t];D(x);y=ch[x][t];ch[i][!t]=y;ch[x][t]=i;if(y)fa[y]=i;if(fa[i])if(ch[fa[i]][0]==i)ch[fa[i]][0]=x;else if(ch[fa[i]][1]==i)ch[fa[i]][1]=x;fa[x]=fa[i];fa[i]=x;U(i);} void spl(int x){int y,z;D(x);while(!tp(x)){y=fa[x];z=fa[y];if(z)D(z);if(y)D(y);if(tp(y))rot(y,ch[y][0]==x);else if(ch[z][0]==y)if(ch[y][0]==x)rot(z,1),rot(y,1);else rot(y,0),rot(z,1);else if(ch[y][0]==x)rot(y,1),rot(z,0);else rot(z,0),rot(y,0);U(x);}} void acc(int x){for(int i=0,t;x;i=x,x=fa[x]){spl(x);t=ch[x][1];if(t)Hins(x,t);ch[x][1]=i;if(i){fa[i]=x;Hdel(x,i);}U(x);}} void maker(int x){acc(x);spl(x);REV(x);} void change(int x,int y){acc(x);spl(x);key[x]=y;U(x);} void cut(int x,int y){maker(x);acc(y);spl(y);ch[y][0]=0;fa[x]=0;U(y);} void link(int x,int y){maker(x);acc(y);spl(y);fa[x]=y;Hins(y,x);U(y);} vector<int> E[N];void dfs(int i){vector<int>::iterator it;ALL(it,E[i])if((*it)!=fa[i])fa[*it]=i,dfs(*it),Hins(i,*it);U(i);} void solve(){pii u;while(1){u=Q.top();if(ans[u.se]==u.fi)break;Q.pop();}printf("%d\n",u.fi);} int main() { freopen("longest.in","r",stdin);freopen("longest.out","w",stdout); read(n,m); rep(i,1,n-1)read(x,y),E[x].pb(y),E[y].pb(x); rep(i,1,n)read(key[i]); dfs(1); solve(); for(;m;m--) { char c=getc(); if(c==‘M‘)read(x,y),change(x,y); else if(c==‘C‘)read(x,y),read(u,v),cut(x,y),link(u,v); solve(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。