c/c++语言开发共享[Vani有约会]雨天的尾巴

我之前考试是遇到过这题，但是数据范围k<=20，状压就能过。

结果原题范围k<=100000……

果断线段树合并。

普及线段树合并：

比如两个相同大小的线段树,将b树各个区间上的值合并到a树上，从树根开始合并，然后递归合并左右儿子，有三种情况：

（假设现在a树遍历到x点，b树遍历到y点）

1.x，y至少其一未被修改过（语文不好勿喷），则将x变为遍历过的那个。

2.x，y位于叶节点（l==r），则sum[x]+=sum[y]。

3.一般情况，递归处理左右儿子，最后更新当前点。

本题中合并如下：

void merge(int &a,int b,int l,int r) {     if(!b)return ;     if(!a){a=b;return ;}     //1     if(l==r){sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;}//注意维护     //2     int mid = (l+r)>>1;     merge(ls[a],ls[b],l,mid);//递归左子树     merge(rs[a],rs[b],mid+1,r);//递归右子树     update(a);     //3 }

juruo代码奉上：

#include<cstdio> #include<algorithm> using namespace std; #define n 100105 inline int rd() {     int f=1,c=0;char ch = getchar();     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}     while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}     return f*c; } int n,m,hed[n],cnt; struct eg {     int to;     int nxt; }e[2*n]; void ae(int f,int t) {     e[++cnt].to = t;     e[cnt].nxt = hed[f];     hed[f] = cnt; } int dep[n],fa[n],son[n],tp[n],siz[n]; void dfs1(int u) {     dep[u]=dep[fa[u]]+1;     siz[u]=1;     for(int j=hed[u];j;j=e[j].nxt)     {         int to = e[j].to;         if(to==fa[u])continue;         fa[to]=u;         dfs1(to);         siz[u]+=siz[to];         if(siz[to]>siz[son[u]])son[u]=to;     } } void dfs2(int u,int topn) {     tp[u]=topn;     if(!son[u])return ;     dfs2(son[u],topn);     for(int j=hed[u];j;j=e[j].nxt)     {         int to = e[j].to;         if(to==fa[u]||to==son[u])continue;         dfs2(to,to);     } } int get_lca(int a,int b) {     while(tp[a]!=tp[b])     {         if(dep[tp[a]]<dep[tp[b]])swap(a,b);         a=fa[tp[a]];     }     return dep[a]<dep[b]?a:b; } int rt[n],sum[70*n],sn[70*n],ls[70*n],rs[70*n],tot; void update(int u) {     sn[u]=sum[ls[u]]>=sum[rs[u]]?sn[ls[u]]:sn[rs[u]];     sum[u]=sum[ls[u]]>=sum[rs[u]]?sum[ls[u]]:sum[rs[u]]; } void insert(int l,int r,int &u,int qx,int d) {     if(!u)u=++tot;     if(l==r)     {         sum[u]+=d;         if(sum[u])sn[u]=l;         else sn[u]=0;         return ;     }     int mid = (l+r)>>1;     if(qx<=mid)insert(l,mid,ls[u],qx,d);     else insert(mid+1,r,rs[u],qx,d);     update(u); } void merge(int &a,int b,int l,int r) {     if(!b)return ;     if(!a){a=b;return ;}     if(l==r){sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;}     int mid = (l+r)>>1;     merge(ls[a],ls[b],l,mid);     merge(rs[a],rs[b],mid+1,r);     update(a); } int ans[n]; void dfs(int u) {     for(int j=hed[u];j;j=e[j].nxt)     {         int to = e[j].to;         if(to==fa[u])continue;         dfs(to);         merge(rt[u],rt[to],1,m);     }     ans[u]=sn[rt[u]]; } struct nd {     int f,t,z; }nd[n]; bool cmp(nd a,nd b) {     return a.z<b.z; } int to[n]; int main() {     n=rd(),m=rd();     for(int f,t,i=1;i<n;i++)     {         f=rd(),t=rd();         ae(f,t),ae(t,f);     }     dfs1(1),dfs2(1,1);     for(int f,t,z,i=1;i<=m;i++)     {         f=rd(),t=rd(),z=rd();         nd[i].f=f,nd[i].t=t,nd[i].z=z;     }     sort(nd+1,nd+1+m,cmp);     int las=-1,k=0;     for(int f,t,z,lca,i=1;i<=m;i++)     {         if(nd[i].z!=las)         {             las=nd[i].z;             to[++k]=nd[i].z;         }         nd[i].z=k;         f = nd[i].f,t = nd[i].t,z = nd[i].z;         lca = get_lca(f,t);         insert(1,m,rt[f],z,1);         insert(1,m,rt[t],z,1);         insert(1,m,rt[lca],z,-1);         if(lca!=1)insert(1,m,rt[fa[lca]],z,-1);     }     dfs(1);     for(int i=1;i<=n;i++)     {         printf("%dn",to[ans[i]]);     }     return 0; }

在这里提一下空间问题：

每进行一次插入，会添加log级的点，因此juruo认为开nlogn级数组即可。