免费 网站 如何做,动态视频网站开发,建设银行网站个人中心,网站上传文件 ftp解析
见到动态维护最远点对#xff0c;不难想到利用 set 维护最大值和次大值#xff0c;每个点维护两个 set 的杂技做法。 但是问题是…T了啊。 咋办嘞。
一个在本题至关重要的 trick#xff1a;利用两个堆来支持访问最大值和删除 具体也很好理解#xff1a;当删除的时候…解析
见到动态维护最远点对不难想到利用 set 维护最大值和次大值每个点维护两个 set 的杂技做法。 但是问题是…T了啊。 咋办嘞。
一个在本题至关重要的 trick利用两个堆来支持访问最大值和删除 具体也很好理解当删除的时候就向第二个堆 push 一个删除元素每次访问的时候先把原堆和删除堆堆顶一样的元素弹掉即可。 支持了删除剩下的就简单了。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define OK printf(ok\n)
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e5100;
const int inf1e9100;
int n,m;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}
int dep[N],q[N1],tot,pl[N];
void dfs0(int x,int f){dep[x]dep[f]1;q[tot]x;pl[x]tot;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dfs0(to,x);q[tot]x;}return;
}
int Min(int x,int y){return dep[x]dep[y]?x:y;
}
int lg[N1],mn[N1][20],mi[20];
void init(){dfs0(1,0);lg[0]-1;for(int i1;itot;i) lg[i]lg[i1]1;mi[0]1;for(int i1;ilg[tot];i) mi[i]mi[i-1]1;for(int i1;itot;i) mn[i][0]q[i];for(int k1;klg[tot];k){for(int i1;imi[k]-1tot;i) mn[i][k]Min(mn[i][k-1],mn[imi[k-1]][k-1]);}return;
}
inline int Lca(int x,int y){xpl[x];ypl[y];if(xy) swap(x,y);int klg[y-x1];//printf( k%d\n,k);return Min(mn[x][k],mn[y-mi[k]1][k]);
}
inline int Dis(int x,int y){int lcaLca(x,y);//printf((%d %d) lca%d dis%d\n,x,y,lca,dep[x]dep[y]-2*dep[lca]);return dep[x]dep[y]-2*dep[lca];
}
vectorintf[2][N];
int w[N],top[N];
int rt,mnn,siz[N],S,son[N];
bool vis[N];
int o;
void findrt(int x,int f){siz[x]1;son[x]0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof||vis[to]) continue;findrt(to,x);siz[x]siz[to];son[x]max(son[x],siz[to]);}son[x]max(son[x],S-siz[x]);if(mnnson[x]){mnnson[x];rtx;}return;
}
int tim;
int solve(int x,int nS){//if(tim%10000) debug(%d\n,x);//printf(??\n);SnS;mnninf;findrt(x,0);xrt;vis[x]1;siz[x]nS1;f[0][x].resize(siz[x]1);f[1][x].resize(siz[x]1);for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]) continue;int tmpsolve(to,nS-son[to]);top[tmp]x;}return x;
}
struct Set{priority_queueintq,d;inline bool empty(){return q.size()d.size();}inline int size(){return q.size()-d.size();}inline void upd(){while(!d.empty()q.top()d.top()) q.pop(),d.pop();}inline int top(){ upd();return q.top();}inline void del(int x){d.push(x);return;}inline void pop(){upd();q.pop();} inline void ins(int x){q.push(x);return;}inline int sec(){upd();int xtop();pop();int ytop();ins(x);return y;}
};
Set s0[N],s1[N],ans;
inline int calc(int x){return s0[x].top()s0[x].sec();
}
void ins(int x,int w){if(s0[x].size()2) ans.del(calc(x));s0[x].ins(w);if(s0[x].size()2) ans.ins(calc(x));return;
}
void era(int x,int w){if(s0[x].size()2) ans.del(calc(x));s0[x].del(w);if(s0[x].size()2) ans.ins(calc(x));return;
}
int op[N],num;
void add(int x){num;//printf(\nadd:%d\n,x);ins(x,0);for(int ix;top[i];itop[i]){if(!s1[i].empty()) era(top[i],s1[i].top());s1[i].ins(Dis(x,top[i]));ins(top[i],s1[i].top());}return;
}
void del(int x){--num;era(x,0);for(int ix;top[i];itop[i]){era(top[i],s1[i].top());s1[i].del(Dis(x,top[i]));if(!s1[i].empty()) ins(top[i],s1[i].top());}return;
}
signed main(){
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();for(int i1;in;i){int xread(),yread();addline(x,y);addline(y,x);}init(); solve(1,n);//for(int i1;in;i) printf(i%d top%d\n,i,top[i]);for(int i1;in;i) add(i);mread();char c;for(int i1;im;i){scanf( %c,c);if(cG){if(!ans.empty()) printf(%d\n,ans.top());else if(num) printf(0\n);else printf(-1\n);}else{int xread();if(op[x]) add(x);else del(x);op[x]^1;}}return 0;
}
/*
*/
