无锡做网站seo的,数据中心网站模板,企业门户网站在信息系统架构中属于哪个层次,威海网站建设怎么样细思极恐#xff0c;我的能力已经退步到这个地步了吗#xff1f;
数据结构
这题的修改是强行加进去迷惑你的。
考虑怎么求树的带权重心。
完了我只会树形dp
完了完了
结论#xff1a;设uuu的子树和为szusz_uszu#xff0c;所有点权值和为sss#xff0c;那么树的带…细思极恐我的能力已经退步到这个地步了吗
数据结构
这题的修改是强行加进去迷惑你的。
考虑怎么求树的带权重心。
完了我只会树形dp
完了完了
结论设uuu的子树和为szusz_uszu所有点权值和为sss那么树的带权重心等价于满足szu≥⌈s2⌉sz_u\ge \lceil\frac{s}{2}\rceilszu≥⌈2s⌉且深度最大的点uuu。
似乎机房大部分人都想到了这一点只有我是joker
道理很简单。显然这个条件是必要的。其次uuu肯定在根节点所在的重链上并且满足条件的点一定是重链的一段前缀容易发现只有这一段前缀的结尾那个点能作为树的重心。
下面的分析就很简单了。
第一种方法我们只要能确定一个点一定在重心的子树内然后从这个点往上跳即可。下一步比较构造考虑在dfn\text{dfn}dfn序中找到第一个满足前缀和≥⌈s2⌉\ge \lceil\frac{s}{2}\rceil≥⌈2s⌉的点这个点一定在重心的子树对应的那段dfn\text{dfn}dfn序上换句话说一定在重心的子树内往上跳即可。注意树的重心可能有两个因此uuu的父亲也可能是重心所以当子树和恰好是s2\frac{s}{2}2s时要返回uuu的父亲。又因为点权可能为零因此最后要先跳一段000再返回父亲。
第二种方法记录上一次重心的位置如果是对链操作那么新的重心一定在链端点的祖先上如果是对子树操作那么新的重心可能在uuu的祖先上也可能在uuu的重链上直接在重链上跳即可。
复杂度O(nlog2n)O(n\log^2 n)O(nlog2n)。
#includebits/stdc.h
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N3e55;
int n,Q,f[N][20],dfn[N],dep[N],tp[N],sz[N],son[N],rk[N],num;
ll sum;
vectorintg[N];
struct node{ll sum,dat;
}t[N2];
void add(int p,int l,int r,ll x){t[p].sum(r-l1)*x,t[p].datx;
}
void pushdown(int p,int l,int r){int midlr1;if(t[p].dat){add(p1,l,mid,t[p].dat),add(p1|1,mid1,r,t[p].dat),t[p].dat0;}
}
void pushup(int p){t[p].sumt[p1].sumt[p1|1].sum;
}
void upd(int p,int l,int r,int ql,int qr,ll x){if(qllrqr){add(p,l,r,x);return;}int midlr1;pushdown(p,l,r);if(qlmid)upd(p1,l,mid,ql,qr,x);if(midqr)upd(p1|1,mid1,r,ql,qr,x);pushup(p);
}
ll qry(int p,int l,int r,int ql,int qr){if(qllrqr)return t[p].sum;int midlr1;pushdown(p,l,r);if(qrmid)return qry(p1,l,mid,ql,qr);if(midql)return qry(p1|1,mid1,r,ql,qr);return qry(p1,l,mid,ql,qr)qry(p1|1,mid1,r,ql,qr);
}
void dfs(int u,int topf){sz[u]1,f[u][0]topf,dep[u]dep[topf]1;for(int i1;i20;i)f[u][i]f[f[u][i-1]][i-1];for(auto v:g[u]){if(v!topf){dfs(v,u),sz[u]sz[v];if(sz[v]sz[son[u]])son[u]v;}}
}
void dfs2(int u,int topf){tp[u]topf,dep[u]dep[topf]1,dfn[u]num,rk[num]u;if(son[u])dfs2(son[u],topf);for(auto v:g[u]){if(!dfn[v])dfs2(v,v);}
}
int Lca(int x,int y){if(dep[x]dep[y])swap(x,y);for(int i19;i0;i--)if(dep[f[x][i]]dep[y])xf[x][i];if(xy)return x;for(int i19;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}
int query(){int l1,rn,res0;sumt[1].sum;while(lr){int midlr1;if(qry(1,1,n,1,mid)(sum1)/2)resmid,rmid-1;else lmid1;}resrk[res];if(qry(1,1,n,dfn[res],dfn[res]sz[res]-1)(sum1)/2){for(int i19;i0;i--){int uf[res][i];if(uqry(1,1,n,dfn[u],dfn[u]sz[u]-1)(sum1)/2)resu;}resf[res][0];}if(qry(1,1,n,dfn[res],dfn[res]sz[res]-1)sum/2){for(int i19;i0;i--){int uf[res][i];if(uqry(1,1,n,dfn[u],dfn[u]sz[u]-1)sum/2)resu;}if(f[res][0])return f[res][0];return res;}return res;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinn;for(int i1;in;i){int u,v;cinuv,g[u].pb(v),g[v].pb(u);}cinQ;dfs(1,0),dfs2(1,1);for(int i1;iQ;i){int op,x,y,w;cinopxy;if(op1){upd(1,1,n,dfn[x],dfn[x]sz[x]-1,y);}else{cinw;int fxtp[x],fytp[y];while(fx!fy){if(dep[fx]dep[fy])upd(1,1,n,dfn[fx],dfn[x],w),xf[fx][0];else upd(1,1,n,dfn[fy],dfn[y],w),yf[fy][0];fxtp[x],fytp[y];}if(dfn[x]dfn[y])swap(x,y);upd(1,1,n,dfn[x],dfn[y],w);}coutquery()\n;}
} 签到
吐槽好好的题为什么要强行套上高精度这样恶心的东西单纯为了恶心选手吗
把容斥的式子写出来(−1)∣S∣(nm−(c−1)∣S∣−∑i∈Sbim)(-1)^{|S|}\binom{nm-(c-1)|S|-\sum_{i\in S}{b^i}}{m}(−1)∣S∣(mnm−(c−1)∣S∣−∑i∈Sbi)
然而直接组合数非常难算。但是注意到mmm很小因此我们可以把组合数看成一个多项式。
刚开始想的是一些比较特殊的情况可以简单递推求出但是发现对于普通的情况难以处理感觉数位dpdpdp部分又比较麻烦于是就一无所获了。
首先把nnn转化成bbb进制然后枚举∣S∣|S|∣S∣。为什么我想不到正解的思路呢 注意到∑i∈Sbi\sum_{i\in S}b^i∑i∈Sbi的数位上都是111因此我们枚举一段前缀就不用考虑负数的情况。问题转化为从1,2,...,m1,2,...,m1,2,...,m中选kkk个数记作集合TTT对于每个i∈[1,m]i\in [1,m]i∈[1,m]求每种情况下(∑j∈Tbj)i(\sum_{j\in T}b_j)^i(∑j∈Tbj)i的和。最简单的想法是每次加入一个数时用二项式定理暴力展开。这可以用O(n4)O(n^4)O(n4)的dpdpdp预处理求出。
总复杂度O(n4)O(n^4)O(n4)。一道将数位dpdpdp容斥多项式高精度强行拼凑的辣鸡的毒瘤签到题 爆搜
不会。只会O(2npoly(n))O(2^n\text{poly}(n))O(2npoly(n))的做法。
似乎大家t2都挂分了但是只有我t2是不会做我好菜啊
