网站开发视频会议插件,中小企业名录查询官网,wordpress首页默认文件夹,建筑行业数据共享平台网站CF372D. Choosing Subtree is Fun
Solution
想了一晚都不会#xff0c;一觉醒来就悟了QwQQwQQwQ 之前一直想着如何用类似树形DPDPDP的方法求出每一个点的贡献再合并#xff0c;然后突然发现直接枚举区间就行了。
考虑区间确定时#xff0c;其实就是求区间内节点在原树上的…CF372D. Choosing Subtree is Fun
Solution
想了一晚都不会一觉醒来就悟了QwQQwQQwQ 之前一直想着如何用类似树形DPDPDP的方法求出每一个点的贡献再合并然后突然发现直接枚举区间就行了。
考虑区间确定时其实就是求区间内节点在原树上的斯坦纳树的点数。 我们枚举左端点lll显然随着lll的增加rrr时非降的因此动态维护斯坦纳树的点数即可。
因为斯坦纳树的边数就是每个关键点的深度和减去dfsdfsdfs序相邻的关键点的LCALCALCA的深度和而点数为边数加一。每次操作会加入一个点删除一个点用setsetset维护关键点的dfsdfsdfs序计算贡献即可。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN400005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
setint Set;
vectorint e[MAXN];
int id[MAXN],dfn[MAXN],DFN0,dep[MAXN],mn[18][MAXN],n,Log[MAXN],sum0,k,ans1,num0,eul[MAXN],ID[MAXN];
void dfs(int x,int father)
{id[dfn[x]DFN]x,dep[x]dep[father]1,ID[eul[x]num]x;for (auto v:e[x])if (v!father) {dfs(v,x);ID[num]x;}
}
void Init()
{for (int i1;inum;i) mn[0][i]dep[ID[i]];for (int i1;i17;i)for (int j1;jnum-(1i)1;j) mn[i][j]min(mn[i-1][j],mn[i-1][j(1(i-1))]);
}
int getdep(int l,int r)
{leul[id[l]],reul[id[r]];if (lr) swap(l,r);int xLog[r-l1];return min(mn[x][l],mn[x][r-(1x)1]);
}
void add(int x)
{setint::iterator itSet.lower_bound(x);int nxt,lst;if (itSet.end()) nxt*Set.begin(),it--,lst*it;else if (itSet.begin()) nxt*it,lst*Set.rbegin();else nxt*it,it--,lst*it;if (nxtlst) sumgetdep(lst,lst)getdep(x,x)-getdep(x,lst)*2;else sumgetdep(x,x)getdep(lst,nxt)-getdep(x,nxt)-getdep(lst,x);Set.insert(x);
}
void del(int x)
{Set.erase(Set.find(x));if (!Set.size()) return; setint::iterator itSet.lower_bound(x);int nxt,lst;if (itSet.end()) nxt*Set.begin(),it--,lst*it;else if (itSet.begin()) nxt*it,lst*Set.rbegin();else nxt*it,it--,lst*it;if (nxtlst) sum-getdep(lst,lst)getdep(x,x)-getdep(x,lst)*2;else sum-getdep(x,x)getdep(lst,nxt)-getdep(x,nxt)-getdep(lst,x);
}
signed main()
{nread(),kread(),ans1;for (int i1,u,v;in;i) uread(),vread(),e[u].PB(v),e[v].PB(u);Log[1]0; for (int i2;in*2;i) Log[i]Log[i1]1;dfs(1,0),Init(),Set.insert(dfn[1]);for (int l1,r1;ln;l){while (rnsum1k) r,add(dfn[r]);if (sum1k) upmax(ans,r-l);else upmax(ans,r-l1);del(dfn[l]);}printf(%d\n,ans);return 0;
}
