题意：一棵n个点的树，其中一些点已经有值，需要给所有没有值的点赋值，使任意相邻的两个点相差恰好为1，求是否可行，可行求一组解。

对所有有值的点建一棵虚树，每个儿子会对父亲的取值范围和奇偶性有一个限制，从下往上dp，如果出现不合法的情况无解。之后虚树上没有值的点会有一个取值范围。从上往下dp，虚树上每个点取范围内任意一个满足奇偶性的值，并对虚树边上的点赋值，最后对不在虚树边上的点赋值。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
const int inf=1e9;
int n,tot,m,cnt,top;
int head[N],nex[N<<1],to[N<<1];
int fa[N][21],deep[N];
int val[N],L[N],R[N],pos[N],a[N],st[N],sig[N];
vector<int>vec[N];
void quit(){puts("No");exit(0);}
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dfs(int x,int y)
{
    fa[x][0]=y;
    for(int i=1;i<=20;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    deep[x]=deep[y]+1;
    pos[x]=++cnt;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
            dfs(to[i],x);
}
int cmp(int x,int y){return pos[x]<pos[y];}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if(deep[fa[x][i]]>=deep[y])x=fa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void dfs1(int x)
{
    L[x]=-inf;R[x]=inf;sig[x]=-1;
    for(int i=0,t,d,v;i<vec[x].size();i++)
    {
        dfs1(t=vec[x][i]);
        d=deep[t]-deep[x];
        v=(R[t]+d)&1;
        L[x]=max(L[x],L[t]-d);
        R[x]=min(R[x],R[t]+d);
        if(sig[x]==-1)sig[x]=v;
        else if(sig[x]!=v)quit();
    }
    if(L[x]>R[x])quit();
    if(val[x]!=val[0])
    {
        if(val[x]<L[x]||val[x]>R[x])quit();
        if(sig[x]!=-1&&(val[x]&1)!=sig[x])quit();
        L[x]=R[x]=val[x];
    }
}
void dfs2(int x)
{
    for(int i=0,t,d,d1;i<vec[x].size();i++)
    {
        t=vec[x][i];
        d=deep[t]-deep[x];
        val[t]=max(L[t],val[x]-d);
        d1=(val[x]+d-val[t])/2;
        int now=val[t],p=t;
        for(int j=1;j<=d1;j++)
            val[fa[p][0]]=val[p]+1,p=fa[p][0];
        for(int j=1;j<d-d1;j++)
            val[fa[p][0]]=val[p]-1,p=fa[p][0];
        dfs2(t);
    }
}
void dfs3(int x,int y)
{
    if(val[x]==val[0])
        val[x]=val[y]+1;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)dfs3(to[i],x);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    memset(val,-0x3f,sizeof(val));
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        scanf("%d",&val[a[i]]);
    }
    dfs(1,0);
    sort(a+1,a+1+m,cmp);
    st[top=1]=1;
    for(int i=1,t;i<=m;i++)
    {
        while((t=lca(a[i],st[top]))!=st[top])
        {
            if(deep[t]>deep[st[top-1]])
            {
                vec[t].push_back(st[top]);
                st[top]=t;
            }
            else
            {
                vec[st[top-1]].push_back(st[top]);
                top--;
            }
        }
        if(st[top]!=a[i])
            st[++top]=a[i];
    }
    for(int i=top;i>1;i--)
        vec[st[i-1]].push_back(st[i]);
    dfs1(1);
    val[1]=L[1];
    dfs2(1);
    dfs3(1,0);
    puts("Yes");
    for(int i=1;i<=n;i++)
        printf("%d\n",val[i]);
    return 0;
}

题意：构造一个长度小于200的字符集为1到100的串，使它的全部非空子序列中恰好有n个为一个好串，其中好串为一个相同的串复制一遍接到后面得到的串。

考虑一个串$$p_1p_2...p_n 1 2 3 4 ... n$$，其中$$p_1p_2...p_n$$为一个排列，子序列中好串数量为排列的不下降子序列数
注意到在一个排列前加一个最大的数导致好串+1，在后面加导致*2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
int cnt;
vector<int>q1,q2;
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%lld",&n);n++;
    int now=100;
    while(n!=1)
    {
        if(n&1)n--,q1.push_back(now--);
        else n>>=1,q2.push_back(now--);
        cnt++;
    }
    printf("%d\n",cnt*2);
    for(int i=0;i<q1.size();i++)printf("%d ",q1[i]);
    for(int i=q2.size()-1;i>=0;i--)printf("%d ",q2[i]);
    for(int i=now+1;i<=100;i++)printf("%d ",i);
    return 0;
}

题意：一行n个球，第i个球有颜色ci和重量wi，两个球如果同色且重量和不超过X 或 不同色且重量和不超过y 就可以交换，求最终可以得到多少不同的颜色序列

如果a,b可以交换， a,c可以交换，那么b,c可以交换。
abc->bac->bca->acb
那么可以交换的一定构成一些团，最多有一个团由不同的颜色的一些重量最小的组成。求出这个团，然后组合数

#include <bits/stdc++.h>
using namespace std;
#define N 210000
#define mod 1000000007
#define ll long long
int n,X,Y,cnt;
int c[N],w[N],a[N],pos[N],num[N],jc[N],njc[N];
vector<int>v1[N],v2[N];
int cmp(int x,int y){return v1[x][0]<v1[y][0];}
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;y>>=1;
    }
    return ret;
}
void init()
{
    jc[0]=njc[0]=1;
    for(int i=1;i<=n;i++)jc[i]=(ll)jc[i-1]*i%mod;
    njc[n]=qpow(jc[n],mod-2);
    for(int i=n-1;i>=1;i--)njc[i]=(ll)njc[i+1]*(i+1)%mod;
}
int C(int x,int y){return (ll)jc[x]*njc[y]%mod*njc[x-y]%mod;}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d%d",&n,&X,&Y);
    init();
    for(int i=1;i<=n;i++)
        scanf("%d%d",&c[i],&w[i]),a[++cnt]=c[i];
    sort(a+1,a+1+cnt);
    cnt=unique(a+1,a+1+cnt)-a-1;
    for(int i=1;i<=n;i++)
    {
        c[i]=lower_bound(a+1,a+1+cnt,c[i])-a;
        v1[c[i]].push_back(w[i]);
    }
    for(int i=1;i<=cnt;i++)
    {
        sort(v1[i].begin(),v1[i].end());
        pos[i]=i;
    }
    sort(pos+1,pos+1+cnt,cmp);
    for(int i=1;i<=cnt;i++)
        v2[i]=v1[pos[i]];
    num[1]=upper_bound(v2[1].begin(),v2[1].end(),X-v2[1][0])-v2[1].begin();
    if(cnt>1)num[1]=max(num[1],
    (int)(upper_bound(v2[1].begin(),v2[1].end(),Y-v2[2][0])-v2[1].begin()));

    for(int i=2;i<=cnt;i++)
    {
        num[i]=upper_bound(v2[i].begin(),v2[i].end(),X-v2[i][0])-v2[i].begin();
        num[i]=max(num[i],
        (int)(upper_bound(v2[i].begin(),v2[i].end(),Y-v2[1][0])-v2[i].begin()));
    }
    int sum=num[1],ans=1;
    for(int i=2;i<=cnt;i++)
    {
        if(v2[i][0]+v2[1][0]>Y)break;
        ans=(ll)ans*C(sum+num[i],sum)%mod;
        sum+=num[i];
    }
    printf("%d\n",ans);
    return 0;
}

题意：有n个兔子，初始时第i个兔子在xi位置，每组有m次跳跃，每组的第i次跳跃为兔子$$a_i$$等概率选$$a_i-1$$或$$a_i+1$$,然后兔子$$a_i$$的位置变为原位置关于选择的兔子位置对称的位置。求进行K组后第i个兔子的期望位置。

每次跳跃相当于把兔子从位置 $$X_i$$ 变为$$X_{i-1} +X_{i+1}-X_i$$

差分之后相当于交换两个数的位置
直接对每个轮换求

#include <bits/stdc++.h>
using namespace std;
#define N 1100000
#define ll long long
ll K;
int n,m,top;
int a[N],p[N],pos[N],vis[N],fin[N],st[N];
ll v[N],v1[N];
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&v[i]),p[i]=i;
    scanf("%d%lld",&m,&K);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        swap(p[a[i]],p[a[i]+1]);
    for(int i=1;i<=n;i++)pos[p[i]]=i;
    for(int i=1,now;i<=n;i++)if(!vis[i])
    {
        st[0]=i;vis[i]=1;top=1;
        now=pos[i];
        while(now!=i)
        {
            st[top]=now;vis[now]=1;top++;
            now=pos[now];
        }
        int t=K%top;
        for(int j=0;j<top;j++)
            fin[st[(j+t)%top]]=st[j];
    }
    v1[1]=v[1];
    for(int i=2;i<=n;i++)v1[i]=v[i]-v[i-1];
    for(int i=1;i<=n;i++)v[i]=v1[fin[i]];
    v1[1]=v[1];
    for(int i=2;i<=n;i++)v1[i]=v[i]+v1[i-1];
    for(int i=1;i<=n;i++)
        printf("%lld.0\n",v1[i]);
    return 0;
}

题意：给出一棵初始所有边都是蓝边的树，每次选一条所有边都是蓝边的简单路径，将路径上一条蓝边断开，在路径两端连一条红边，问是否可以转变成规定的所有边都是红边的树。

将红树的每条边视为蓝树上一条路径，每次找一条蓝树上只被一条路径覆盖的边，把这条路径删掉。如果找不到，那么无解
可以用树剖+线段树+set维护，线段树维护两个标记表示子树中是否有被覆盖一次和零次的边。标记永久化
复杂度$$O(nlog^3n)$$

#include <bits/stdc++.h>
using namespace std;
#define N 110000
#define ls l,mid,now<<1
#define rs mid+1,r,now<<1|1
int n,tot,cnt,ret;
int head[N],nex[N<<1],to[N<<1];
int deep[N],fa[N],son[N],size[N],top[N],pos[N],bel[N];
int X[N],Y[N],num[N<<2],v0[N<<2],v1[N<<2];
set<int>se[N<<2];
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dfs1(int x,int y)
{
    size[x]=1;
    fa[x]=y;deep[x]=deep[y]+1;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
        {
            dfs1(to[i],x);
            size[x]+=size[to[i]];
            son[x]=size[to[i]]>size[son[x]] ? to[i] : son[x]; 
        }
}
void dfs2(int x,int y,int tp)
{
    top[x]=tp;
    pos[x]=++cnt;bel[cnt]=x;
    if(son[x])dfs2(son[x],x,tp);
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y&&to[i]!=son[x])
            dfs2(to[i],x,to[i]);
}
void pushup(int l,int r,int now)
{
    if(l==r)
    {
        v0[now]=(num[now]==0);
        v1[now]=(num[now]==1);
        return;
    }
    if(num[now]==0)v0[now]=v0[now<<1]|v0[now<<1|1];
    else v0[now]=0;

    if(num[now]==0)v1[now]=v1[now<<1]|v1[now<<1|1];
    else if(num[now]==1)v1[now]=v0[now<<1]|v0[now<<1|1];
    else v1[now]=0;
}
void insert(int l,int r,int now,int lq,int rq,int p)
{
    if(lq<=l&&r<=rq)
    {
        se[now].insert(p);
        num[now]++;
        pushup(l,r,now);
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=lq)insert(ls,lq,rq,p);
    if(mid<rq) insert(rs,lq,rq,p);
    pushup(l,r,now);
}
void mark(int x,int y,int p)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        insert(1,n,1,pos[top[x]],pos[x],p);
        x=fa[top[x]];
    }
    if(x!=y)
    {
        if(deep[x]<deep[y])swap(x,y);
        insert(1,n,1,pos[y]+1,pos[x],p);
    }
}
void update(int l,int r,int now,int v)
{
    if(num[now])
    {
        ret=*(se[now].begin());
        v=0;
    }
    if(l==r)return;
    int mid=(l+r)>>1;
    if((v==0&&v0[now<<1])||(v==1&&v1[now<<1]))
        update(ls,v);
    else update(rs,v);
}
void del(int l,int r,int now,int lq,int rq,int p)
{
    if(lq<=l&&r<=rq)
    {
        se[now].erase(p);
        num[now]--;
        pushup(l,r,now);
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=lq)del(ls,lq,rq,p);
    if(mid<rq) del(rs,lq,rq,p);
    pushup(l,r,now);    
}
void del(int x,int y,int p)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        del(1,n,1,pos[top[x]],pos[x],p);
        x=fa[top[x]];
    }
    if(x!=y)
    {
        if(deep[x]<deep[y])swap(x,y);
        del(1,n,1,pos[y]+1,pos[x],p);
    }   
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    for(int i=1;i<=n<<2;i++)v0[i]=1;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&X[i],&Y[i]);
        mark(X[i],Y[i],i);
    }
    for(int i=1;i<n;i++)
    {
        if(!v1[1])return puts("NO"),0;
        update(1,n,1,1);
        del(X[ret],Y[ret],ret);
    }
    puts("YES");
    return 0;
}