响应式企业网站设计与实现,设计网站怎么做的,电子商务平台及核心技术,php网站服务建设解析
毒题 细节有亿点点多
我一开始的思路是没有问题的 尝试统计有多少种方案能砍出大小在一个区间的子树、 当时的想法是线段树合并 但是这个玩意在需要保留原树的情况下空间复杂度炸没了… 因为我垃圾的实现一个dfs里面就玩了七遍merge函数… 空间常数飞起 然后分数就和暴力…解析
毒题 细节有亿点点多
我一开始的思路是没有问题的 尝试统计有多少种方案能砍出大小在一个区间的子树、 当时的想法是线段树合并 但是这个玩意在需要保留原树的情况下空间复杂度炸没了… 因为我垃圾的实现一个dfs里面就玩了七遍merge函数… 空间常数飞起 然后分数就和暴力一毛一样 qwq
考虑一些更灵巧的做法 动态维护一个关于值域的树状数组 要求一个子树内的答案用遍历到子树根前后的结果相减 子树外就是最终的结果减去子树内结果 然后我这个垃圾的实现似乎还需要再开一个树状数组动态维护返祖链的答案… 虽然实现还是垃圾但是树状数组就可以承受这么恶心的常数了 细节有亿点点多 但调来调去终于算调过去了 qwq
在dfs上动态维护一个树状数组是一个值得学习的好思想 不要动不动就开权值线段树暴力搞
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N3e5100;
const double eps1e-6;
const int mod1333331;
inline ll read() {ll x0,f1;char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
int n;
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;
}int mx[N],sec[N],siz[N],mxson[N],secson[N];
void dfs(int x,int f) {siz[x]1;for(int ifi[x]; ~i; ip[i].nxt) {int top[i].to;if(tof) continue;dfs(to,x);siz[x]siz[to];int osiz[to],ooto;if(omx[x]) swap(o,mx[x]),swap(oo,mxson[x]);if(osec[x]) swap(o,sec[x]),swap(oo,secson[x]);}//printf(x%d siz%d mx%d-%d sec%d-%d\n,x,siz[x],mxson[x],mx[x],secson[x],sec[x]);return;
}
ll ans0;
struct tree{int f[N];inline void add(int p,int v1){for(;pn;pp-p) f[p]v;return;}inline int ask(int p){//printf(%d\n,p);int res0;for(;p;p-p-p) resf[p];return res;}
}t1,t2;
struct query{int l,r,val;
}Add[N];
int tot;
void solve(int u,int f) {t1.add(siz[u]);t2.add(siz[u]);int st,ed,l,r,x,y,res0;st1,edn;xn-siz[u];ymx[u];while(sted) {int o(sted)1;if(x-o(n-o)/2) edo;else sto1;//if(u4) printf( st%d ed%d o%d\n,st,ed,o);}lst;//printf(l%d\n,l);rmin(x,n-2*y);//ln-l;rn-r;swap(l,r);int al,br;if(ab) rest1.ask(b)-t1.ask(a-1)-(t2.ask(b)-t2.ask(a-1)),Add[tot](query){a,b,u};if(lr) rest2.ask(n-l)-t2.ask(n-r-1);//printf(---u%d x%d y%d (%d %d) res%d\n,u,x,y,a,b,res);for(int ifi[u];~i;ip[i].nxt){int top[i].to;if(tof) continue;xsiz[to],ymax(tomxson[u]?sec[u]:mx[u],n-siz[u]);st1,edn;while(sted) {int o(sted)1;if(x-o(n-o)/2) edo;else sto1;}lst;rmin(x,n-2*y);if(lr) res-t1.ask(r)-t1.ask(l-1);solve(to,u);if(lr) rest1.ask(r)-t1.ask(l-1);//printf( u%d to%d (%d %d) res%d\n,u,to,l,r,res);}if(ab) res-t1.ask(b)-t1.ask(a-1);//printf(u%d res%d\n\n,u,res);ans1ll*res*u;t2.add(siz[u],-1);return;
}int main() {/*#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endif*///printf(%d\n,sizeof(rub)/1024/1024);int Tread();while(T--) {memset(t1.f,0,sizeof(t1.f));memset(t2.f,0,sizeof(t2.f));memset(fi,-1,sizeof(fi));cnt-1;memset(mx,0,sizeof(mx));memset(sec,0,sizeof(sec));totans0;nread();for(int i1; in; i) {int xread(),yread();addline(x,y);addline(y,x);}dfs(1,0);solve(1,0);//printf(\n);for(int i1;itot;i){ans1ll*Add[i].val*(t1.ask(Add[i].r)-t1.ask(Add[i].l-1));//printf(add:i%d num%d\n,Add[i].val,t1.ask(Add[i].r)-t1.ask(Add[i].l-1));}printf(%lld\n,ans);}return 0;
}
/*
*/
