T1最小生成链(msc)
题意
定义一张图的生成链是原图的一棵生成树，且这棵树退化成一条链。
我们称一条生成链是原图的最小生 成链，当且仅当它当中边权最大的边是原图的所有生成链中最小的。
现有一个 n个点的完全图，点编号为 1到n 。另给出一个长度为 n的序列 ai，完全图中第 i个点与第 j个点间的边的边权为ai^aj 。
请你找出该完全图的最小生成链。但由于答案可能很多，你只需要输出这条最小生成链中边权最大的边 的边权即可
solution
首先我们发现求的是一个序列，其中相邻两个值的最大异或值最小
考虑二进制位，我们把第一个不是全部相同的位取出来（因为全部相同的话答案在这位上就是0）
把这位上值为0的归为1类，其他归为1类
那么相邻两个数的最大值肯定是出现在i，i+1所属类不同的情况
所以我们暴力枚举两个集合 ，建个01trie都做到这一步了谁会这么傻
就好了
code
#include<bits/stdc++.h> #define N 210004 #define ll long long using namespace std; int n; ll a[N]; int ch[N*60][2]; int cnt=0; int kl=-1; void insert(ll k){ int now=0; for(int i=59;i>=0;i--){ int to=(((1LL<<i)&k)>0?1:0); if(!ch[now][to])ch[now][to]=++cnt; now=ch[now][to]; } } ll ask(ll k){//这里ll写成int挂了1个小时QAQAQAQ ll res=0; int now=0; for(int i=59;i>=0;i--){ int to=(((1LL<<i)&k)>0?1:0); if(ch[now][to])now=ch[now][to]; else {res=res|(1LL<<i),now=ch[now][to^1];} } return res; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",a+i); sort(a+1,a+n+1); ll pok=(a[1]^a[n]); for(int i=59;i>=0;i--) if((pok&(1LL<<i))>0){kl=i;break;} if(kl==-1)return puts("0"),0; ll ans=1e18; for(int i=n;i>=1;i--){ if(((1LL<<kl)&a[i])>0){insert(a[i]);} else {ans=min(ans,ask(a[i]));} } printf("%lld\n",ans); }
B. 穿越(across)
题意
就在不久前，Z 国科学家发明了空间穿越器，它能快速地到达指定地点，但是它也有一个很大的缺陷， 只要目的地被设定之后就再也不能更改目的地。而现在，空间穿越器已经被投入使用。 Z 国有一座首都，除此之外还有n 座城市，为了便于描述，我们把首都编号为 0，其它城市从 1编号到n 。由于空间穿越器成本高昂，每座城市只能使用至多两座空间穿越器，而首都城市作为 Z 国的行政中 心，所有城市必须要有一座空间穿越器通向首都（包括首都）。除此之外，每座城市还会有一个空间穿 越器通向xi 号城市。Z 国不会让另一座空间穿越器也通向首都，但不保证空间穿越器不会通向其所在城 市。空间穿越器只负责将指定的东西送至目的地，并不能将目的地的东西接回来。 空间穿越器非常大地方便了 Z 国交通，同时也促进了 Z 国旅游业的发展。但是不久以后，旅行者们发现 了问题：由于空间穿越器是单向的，这就导致他们不一定能很方便地回到自己的城市。为了调查这样的 情况，Z 国国主需要你告诉他经过m 次穿越，分别从 Z 国的(n+1) 座城市出发回到出发地有多少种穿 越方法，两种方法不同当且仅当某一次穿越使用的空间穿越器不同。 经过 Z 国计算学会一个月的研究，他们发现答案可能很大，于是 Z 国国主只要你将答案模 998244353后 输出即可。
solution 不会nya~
T3树统计(count)
题意
有一棵 n个节点的树，以1 号点为根。每个点有一个整数点权ai，点权可能为正也可能为负。 我们定义一棵树是美妙的，当且仅当这棵树所有点的点权都是非负整数。 原树不一定是美妙的。我们希望通过施加一些魔法使得这棵树成为一棵美妙的树。 一次魔法可任意选取选取一个点 u和一个正整数 w，设 u点父亲节点是 f，那么进行一次魔法后，可以使得 u点点权加上 w，而使 f点点权减去w。 我们需要你回答是否可能通过施加若干次魔法使这棵树成为一棵美妙的树。 相信你已经会做这道题了。但是本题作为此次比赛的压轴，肯定是不会这么简单的。 我们让这棵树进行 m次变化，每次变化会指定一个点 x和一个整数 w，这里 w可能是正整数、零或负 整数。意为将点x 的点权加上w 。 你需要在每一次变化后回答是否可能通过施加魔法使这棵树称为一棵美妙的树。 注意：每次变化是永久有效的，前面对点权的变化会直接修改原树的点权。而每次询问时只询问是否可 能，并不真正施加魔法。详见样例解释。
solution:无脑ddp
code
//awsl
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define N 200005 #define int long long using namespace std; const int inf=1e18; int id[N],mp[N],ed[N],top[N],son[N],f[N],siz[N],dp[N],a[N]; int idx=0,n,m; struct zero{ int nxt,to; }edge[N<<1]; int head[N],tot=0; void add_edge(int a,int b){edge[++tot]=(zero){head[a],b};head[a]=tot;} void dfs1(int x,int fa){ siz[x]=1,son[x]=0; for(int i=head[x];i;i=edge[i].nxt){ int to=edge[i].to; if(to==fa)continue;f[to]=x; dfs1(to,x);if(siz[to]>siz[son[x]])son[x]=to;siz[x]+=siz[to]; }} void dfs2(int x,int topf){ mp[id[x]=ed[topf]=++idx]=x;top[x]=topf; if(son[x])dfs2(son[x],topf); for(int i=head[x];i;i=edge[i].nxt){ int to=edge[i].to;if(to==f[x]||to==son[x])continue; dfs2(to,to); }} struct mar{ int kk[2][2]; mar(){kk[0][1]=kk[0][0]=kk[1][0]=kk[1][1]=inf;} friend mar operator *(const mar& a,const mar& b){ mar c; for(int i=0;i<2;i++)for(int r=0;r<2;r++)for(int p=0;p<2;p++) c.kk[i][r]=min(c.kk[i][r],a.kk[i][p]+b.kk[p][r]); return c; } }val[N]; mar op(int a,int b,int c,int d){mar p;p.kk[0][0]=a,p.kk[0][1]=b,p.kk[1][0]=c,p.kk[1][1]=d;return p;} void dfs3(int x){ int dpl=dp[x]=a[x]; if(son[x])dfs3(son[x]),dp[x]+=min(dp[son[x]],0ll); for(int i=head[x];i;i=edge[i].nxt){ int to=edge[i].to; if(to==f[x]||to==son[x])continue; dfs3(to);dpl+=min(dp[to],0ll);dp[x]+=min(0ll,dp[to]); } val[x]=op(dpl,dpl,inf,0); } struct sett{ #define ls (x<<1) #define rs (x<<1|1) #define mid ((l+r)>>1) mar data[N<<2]; void build(int x,int l,int r){ if(l==r){data[x]=val[mp[l]];return;} build(ls,l,mid),build(rs,mid+1,r); data[x]=data[ls]*data[rs]; } void modify(int x,int l,int r,int pos){ if(l==r){data[x]=val[mp[l]];return;} if(pos<=mid)modify(ls,l,mid,pos); else modify(rs,mid+1,r,pos); data[x]=data[ls]*data[rs]; } mar query(int x,int l,int r,int nl,int nr){ if(nl<=l&&r<=nr){return data[x];} if(mid<nl)return query(rs,mid+1,r,nl,nr); else if(mid>=nr)return query(ls,l,mid,nl,nr); else return query(ls,l,mid,nl,nr)*query(rs,mid+1,r,nl,nr); } }dacrp; void update(int x,int v){ val[x].kk[0][0]+=v,val[x].kk[0][1]+=v; while(x){ int now=top[x]; mar las=dacrp.query(1,1,n,id[now],ed[now]);dacrp.modify(1,1,n,id[x]); mar iop=dacrp.query(1,1,n,id[now],ed[now]);x=f[now]; val[x].kk[0][0]+=min(iop.kk[0][0],iop.kk[0][1])-min(las.kk[0][0], las.kk[0][1]); val[x].kk[0][1]=val[x].kk[0][0]; } } signed main(){ scanf("%lld",&n); for(int i=1;i<=n;i++)scanf("%lld",a+i); for(int i=1,aa,b;i<n;i++){scanf("%lld%lld",&aa,&b);add_edge(aa,b),add_edge(b,aa);} dfs1(1,0);dfs2(1,1);dfs3(1); dacrp.build(1,1,n);mar ans=dacrp.query(1,1,n,id[1],ed[1]);(min(ans.kk[0][0],ans.kk[0][1])>=0)?puts("Yes"):puts("No"); scanf("%lld",&m); for(int i=1;i<=m;i++){ int a,b;scanf("%lld%lld",&a,&b); update(a,b);mar ans=dacrp.query(1,1,n,id[1],ed[1]); (min(ans.kk[0][0],ans.kk[0][1])>=0)?puts("Yes"):puts("No"); } }