【学习笔记】NOIP暴零赛2

细思极恐，我的能力已经退步到这个地步了吗？

数据结构

这题的修改是强行加进去迷惑你的。

考虑怎么求树的带权重心。

完了我只会树形dp

完了完了

结论：设$u$的子树和为$s{z}_u$，所有点权值和为$s$，那么树的带权重心等价于，满足$s{z}_u\ge \lceil \frac{s}{2}\rceil$且深度最大的点$u$。

似乎机房大部分人都想到了这一点，只有我是joker？？？

道理很简单。显然这个条件是必要的。其次，$u$肯定在根节点所在的重链上，并且满足条件的点一定是重链的一段前缀，容易发现只有这一段前缀的结尾那个点能作为树的重心。

下面的分析就很简单了。

第一种方法，我们只要能确定一个点一定在重心的子树内，然后从这个点往上跳即可。下一步比较构造，考虑在$\text{dfn}$序中找到第一个满足前缀和$\ge \lceil \frac{s}{2}\rceil$的点，这个点一定在重心的子树对应的那段$\text{dfn}$序上，换句话说一定在重心的子树内，往上跳即可。注意树的重心可能有两个，因此$u$的父亲也可能是重心，所以当子树和恰好是$\frac{s}{2}$时要返回$u$的父亲。又因为点权可能为零，因此最后要先跳一段$0$再返回父亲。

第二种方法，记录上一次重心的位置，如果是对链操作，那么新的重心一定在链端点的祖先上，如果是对子树操作，那么新的重心可能在$u$的祖先上，也可能在$u$的重链上，直接在重链上跳即可。

复杂度$O(n{\log }^{2}n)$。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=3e5+5;
int n,Q,f[N][20],dfn[N],dep[N],tp[N],sz[N],son[N],rk[N],num;
ll sum;
vector<int>g[N];
struct node{ll sum,dat;
}t[N<<2];
void add(int p,int l,int r,ll x){t[p].sum+=(r-l+1)*x,t[p].dat+=x;
}
void pushdown(int p,int l,int r){int mid=l+r>>1;if(t[p].dat){add(p<<1,l,mid,t[p].dat),add(p<<1|1,mid+1,r,t[p].dat),t[p].dat=0;}
}
void pushup(int p){t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void upd(int p,int l,int r,int ql,int qr,ll x){if(ql<=l&&r<=qr){add(p,l,r,x);return;}int mid=l+r>>1;pushdown(p,l,r);if(ql<=mid)upd(p<<1,l,mid,ql,qr,x);if(mid<qr)upd(p<<1|1,mid+1,r,ql,qr,x);pushup(p);
}
ll qry(int p,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return t[p].sum;int mid=l+r>>1;pushdown(p,l,r);if(qr<=mid)return qry(p<<1,l,mid,ql,qr);if(mid<ql)return qry(p<<1|1,mid+1,r,ql,qr);return qry(p<<1,l,mid,ql,qr)+qry(p<<1|1,mid+1,r,ql,qr);
}
void dfs(int u,int topf){sz[u]=1,f[u][0]=topf,dep[u]=dep[topf]+1;for(int i=1;i<20;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 i=19;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];if(x==y)return x;for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];return f[x][0];
}
int query(){int l=1,r=n,res=0;sum=t[1].sum;while(l<=r){int mid=l+r>>1;if(qry(1,1,n,1,mid)>=(sum+1)/2)res=mid,r=mid-1;else l=mid+1;}res=rk[res];if(qry(1,1,n,dfn[res],dfn[res]+sz[res]-1)<(sum+1)/2){for(int i=19;i>=0;i--){int u=f[res][i];if(u&&qry(1,1,n,dfn[u],dfn[u]+sz[u]-1)<(sum+1)/2)res=u;}res=f[res][0];}if(qry(1,1,n,dfn[res],dfn[res]+sz[res]-1)==sum/2){for(int i=19;i>=0;i--){int u=f[res][i];if(u&&qry(1,1,n,dfn[u],dfn[u]+sz[u]-1)==sum/2)res=u;}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);cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v,g[u].pb(v),g[v].pb(u);}cin>>Q;dfs(1,0),dfs2(1,1);for(int i=1;i<=Q;i++){int op,x,y,w;cin>>op>>x>>y;if(op==1){upd(1,1,n,dfn[x],dfn[x]+sz[x]-1,y);}else{cin>>w;int fx=tp[x],fy=tp[y];while(fx!=fy){if(dep[fx]>dep[fy])upd(1,1,n,dfn[fx],dfn[x],w),x=f[fx][0];else upd(1,1,n,dfn[fy],dfn[y],w),y=f[fy][0];fx=tp[x],fy=tp[y];}if(dfn[x]>dfn[y])swap(x,y);upd(1,1,n,dfn[x],dfn[y],w);}cout<<query()<<"\n";} 
} 

签到

吐槽：好好的题，为什么要强行套上高精度这样恶心的东西？单纯为了恶心选手吗？

把容斥的式子写出来：$$(-1{)}^{|S|}(\genfrac{}{}{0ex}{}{n+m-(c-1)|S|-{\sum }_{i\in S}{b}^i}{m})$$

然而直接组合数非常难算。但是注意到$m$很小，因此我们可以把组合数看成一个多项式。

刚开始想的是一些比较特殊的情况，可以简单递推求出，但是发现对于普通的情况难以处理，感觉数位$dp$部分又比较麻烦于是就一无所获了。

首先把$n$转化成$b$进制，然后枚举$|S|$。为什么我想不到正解的思路呢 注意到${\sum }_{i\in S}{b}^i$的数位上都是$1$，因此我们枚举一段前缀就不用考虑负数的情况。问题转化为，从$1,2,...,m$中选$k$个数，记作集合$T$，对于每个$i\in [1,m]$，求每种情况下$({\sum }_{j\in T}{b}_j{)}^i$的和。最简单的想法是，每次加入一个数时，用二项式定理暴力展开。这可以用$O(n^4)$的$dp$预处理求出。

总复杂度$O(n^4)$。一道将数位$dp$，容斥，多项式，高精度强行拼凑的辣鸡的毒瘤签到题

爆搜

不会。只会$O(2^n\text{poly}(n))$的做法。

似乎大家t2都挂分了，但是只有我t2是不会做，我好菜啊？？？