开局开 T3，开出正解之后不想写，直接摆了。于是整场变成了口胡场。两个小时 T3，两个小时 T1。那我要是真写 T3 了我肯定车不出 T1。
赛后看看题解，发现 T1 和正解对上了，T3 也没问题。
lyin 阿克了，无限膜拜。
全篇都是一边睡觉一边写的，有点神志不清所以可能语言很混乱。
线性代数
一开始一直手模规律模不出来，以为是拆二进制位拼起来。然后细想了一下发现这不是数线性基吗，冲个数位 dp 就行了。
数高斯消元之后的线性基，设 \(dp_{i,j}\) 为到第 \(i\) 位线性基有 \(j\) 个数的方案数。每次插入一个新的数，规定其他都是 \(0\)，或者选奇或偶个异或起来。
一开始以为和题解不是一个东西，想了想好像差不多。那不想了。睡。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod=1000000007;
int n,dp[50][50];
int dfs(int x,int cnt,bool mx){
if(x<0)return 1;
if(!mx&&~dp[x][cnt])return dp[x][cnt];
int ans=0,lim=mx?((n>>x)&1):1;
for(int i=0;i<=lim;i++){
int ret=1;
if(i==1&&cnt==0)continue;
if(cnt)ret=1<<cnt-1;
ans=(ans+1ll*ret*dfs(x-1,cnt,mx&&i==lim))%mod;
}
if(lim==1)ans=(ans+dfs(x-1,cnt+1,mx))%mod;
if(!mx)dp[x][cnt]=ans;
return ans;
}
int main(){
memset(dp,-1,sizeof(dp));
scanf("%d",&n);
printf("%d\n",dfs(31,0,true));
return 0;
}
森林
不会。被薄纱了。为什么都会这题，被薄纱了。A 老师说这是套路题，被薄纱了。看了 A 老师题解终于看懂了。基本复读。
经典结论：树上点集是连通块则点数 \(-\) 边数是 \(1\)。那么可以统计 \(T_2\) 上的链并记录 \(T_1\) 的点数减边数的最小值和个数来统计答案。然后为了方便先重标号成 dfs 序。
考虑链的情况，可以线段树扫描线。对 \(T_1\) 的边 \((u,v)\)，在 \(v\) 处对 \([1,u]\) 区间 \(-1\)，每次统计最小值和个数。
然后放到树上。这时线段树的每个叶子维护到其他所有点的最小值和个数。对 \(T_1\) 的一条边 \((u,v)\)，只要在进入 \(u\) 的时候在 \(v\) 有贡献的那半边子树减 \(1\)，\(v\) 同样操作。注意调整 dfs 序。注意这样的话不是单个点的所有链会算两次。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
int n;
struct gra{
int v,next;
}edge[400010];
int t,head[100010][2];
void add(int u,int v,int id){
edge[++t].v=v;edge[t].next=head[u][id];head[u][id]=t;
}
int num,dfn[100010],size[100010],dep[100010],fa[100010][20],rk[200010];
bool v[100010];
long long ans;
void dfs1(int x,int f){
dfn[x]=++num;size[x]=1;dep[x]=dep[f]+1;
rk[dfn[x]]=rk[dfn[f]]+1;v[x]=true;fa[x][0]=f;
for(int i=1;i<20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x][0];i;i=edge[i].next){
if(v[edge[i].v])rk[dfn[x]]--;
}
for(int i=head[x][1];i;i=edge[i].next){
if(edge[i].v!=f){
dfs1(edge[i].v,x);
size[x]+=size[edge[i].v];
}
}
v[x]=false;
}
int getfa(int x,int y){
for(int i=19;i>=0;i--)if(dep[y]<dep[fa[x][i]])x=fa[x][i];
if(fa[x][0]==y)return x;
return -1;
}
struct node{
int min,cnt,lz;
}tree[400010];
void pushup(int rt){
if(tree[lson].min==tree[rson].min)tree[rt].min=tree[lson].min,tree[rt].cnt=tree[lson].cnt+tree[rson].cnt;
else if(tree[lson].min<tree[rson].min)tree[rt].min=tree[lson].min,tree[rt].cnt=tree[lson].cnt;
else tree[rt].min=tree[rson].min,tree[rt].cnt=tree[rson].cnt;
}
void pushtag(int rt,int val){
tree[rt].min+=val;tree[rt].lz+=val;
}
void pushdown(int rt){
if(tree[rt].lz){
pushtag(lson,tree[rt].lz);pushtag(rson,tree[rt].lz);
tree[rt].lz=0;
}
}
void build(int rt,int l,int r){
tree[rt].min=tree[rt].cnt=tree[rt].lz=0;
if(l==r){
tree[rt].min=rk[l];tree[rt].cnt=1;
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(rt);
}
void update(int rt,int L,int R,int l,int r,int val){
if(l<=L&&R<=r){
pushtag(rt,val);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,L,mid,l,r,val);
if(mid<r)update(rson,mid+1,R,l,r,val);
pushup(rt);
}
int query(int rt,int L,int R,int pos){
if(L==R)return tree[rt].min;
pushdown(rt);
int mid=(L+R)>>1;
if(pos<=mid)return query(lson,L,mid,pos);
else return query(rson,mid+1,R,pos);
}
vector<int>pos[100010];
void dfs2(int x,int f){
if(tree[1].min==1)ans+=tree[1].cnt;
for(int i=head[x][0];i;i=edge[i].next){
int ret=getfa(edge[i].v,x);
if(ret!=-1)pos[ret].push_back(edge[i].v);
}
for(int i=head[x][1];i;i=edge[i].next){
if(edge[i].v==f)continue;
update(1,1,n,dfn[edge[i].v],dfn[edge[i].v]+size[edge[i].v]-1,-1);
if(dfn[edge[i].v]>1)update(1,1,n,1,dfn[edge[i].v]-1,1);
if(dfn[edge[i].v]+size[edge[i].v]<=n)update(1,1,n,dfn[edge[i].v]+size[edge[i].v],n,1);
for(int p:pos[edge[i].v])update(1,1,n,dfn[p],dfn[p]+size[p]-1,1);
for(int j=head[edge[i].v][0];j;j=edge[j].next){
if(dfn[edge[j].v]<dfn[edge[i].v]||dfn[edge[i].v]+size[edge[i].v]<=dfn[edge[j].v]){
int ret=getfa(edge[i].v,edge[j].v);
if(ret==-1)update(1,1,n,dfn[edge[j].v],dfn[edge[j].v]+size[edge[j].v]-1,-1);
else{
if(dfn[ret]>1)update(1,1,n,1,dfn[ret]-1,-1);
if(dfn[ret]+size[ret]<=n)update(1,1,n,dfn[ret]+size[ret],n,-1);
}
}
}
dfs2(edge[i].v,x);
update(1,1,n,dfn[edge[i].v],dfn[edge[i].v]+size[edge[i].v]-1,1);
if(dfn[edge[i].v]>1)update(1,1,n,1,dfn[edge[i].v]-1,-1);
if(dfn[edge[i].v]+size[edge[i].v]<=n)update(1,1,n,dfn[edge[i].v]+size[edge[i].v],n,-1);
for(int p:pos[edge[i].v])update(1,1,n,dfn[p],dfn[p]+size[p]-1,-1);
for(int j=head[edge[i].v][0];j;j=edge[j].next){
if(dfn[edge[j].v]<dfn[edge[i].v]||dfn[edge[i].v]+size[edge[i].v]<=dfn[edge[j].v]){
int ret=getfa(edge[i].v,edge[j].v);
if(ret==-1)update(1,1,n,dfn[edge[j].v],dfn[edge[j].v]+size[edge[j].v]-1,1);
else{
if(dfn[ret]>1)update(1,1,n,1,dfn[ret]-1,1);
if(dfn[ret]+size[ret]<=n)update(1,1,n,dfn[ret]+size[ret],n,1);
}
}
}
}
}
void clear(){
ans=0;t=0;num=0;
for(int i=1;i<=n;i++){
head[i][0]=head[i][1]=0;
pos[i].clear();
}
}
int main(){
int tim;scanf("%d",&tim);
while(tim--){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v,0);add(v,u,0);
}
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v,1);add(v,u,1);
}
dfs1(1,0);build(1,1,n);dfs2(1,0);
printf("%lld\n",(ans-n>>1)+n);
clear();
}
return 0;
}
字符串
简单题。感觉做法和题解差不多。赛时跟 joke3579 一起嘴巴这题，他叨叨半天我没听懂什么东西。于是自己搞了下，得到的结果不太一样。
首先看到这种东西看着就想上个 endpos。于是就线段树合并搞一下。然后这个显然是可以贪心在右端点放的，一次操作就是找到最靠左的右端点然后跳过一段。查询长 \(L\) 的串的复杂度就是 \(O(\dfrac nL\log n)\)。
看见这个分数就想着根号分治。那设个阈值 \(B\)，当 \(L>B\) 时在线段树上跳，考虑剩下的串。其实可以预处理。
预处理的方法：把每个位置结尾的长度不超过 \(B\) 的串塞进 unordered_map，然后从左到右扫位置。扫到位置 \(i\) 时更新这个位置结尾的长度不超过 \(B\) 的串，使它们答案 \(+1\)，并打标记使它们在一段长度内不再被统计。复杂度是 \(O(nB)\)。
取 \(B=\sqrt{n\log n}\)，得到复杂度 \(O(n\sqrt{n\log n})\)。场上觉得写起来巨大烦人就开始口胡了。lyin 说块长要调。
没什么想写的欲望。感觉不如去冲 AGC。回头等没人注意去贺一份。据说卡常千奇百怪，那更不想写了。
标签：dfn,省选,update,ret,int,edge,联测,武汉,include From： https://www.cnblogs.com/gtm1514/p/17227234.html