Day 树论

Posted on By 陈, 禹宸 Day 树论无评论

例题精讲（

T1~6显然大家都会，就不讲了

T7：link

题目描述：

每次删去一条边x，设F[x]=其形成的两颗树的重心的和，对F[1~n-1]求和

题解：

重心有许多优秀的性质：

1. 重心一定在重链上
2. 如果有两个重心，两个重心一定是相连的
3. 重心的定义（存在单调性）

性质2很好证明：若不相连，则一定能往中间点合并形成新的重心

性质1可以感性证明，详细证明要用到T4的最远点对一定在直径（重链）上

结合性质三，不难推出一个在重链上二分的做法

如果一个点是另一个点的重儿子咋办？

存次长链啊！

#include <bits/stdc++.h>
using namespace std;
#define N 300005
int vva[N*2],T,n,x,y,I,cnt,tot,he[N],ne[N*2],to[N*2],sz[N],mf[N],ms[N],mi[N],in[N],ou[N],rt[N*2],s[N*60],ls[N*60],rs[N*60];
long long g;
void add(int x,int y) {
    to[cnt]=y;
    ne[cnt]=he[x];
    he[x]=cnt++;
}
void ins(int &x,int y,int l,int r,int p) {
    x=++tot;
    s[x]=s[y]+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(p<=mid) rs[x]=rs[y],ins(ls[x],ls[y],l,mid,p);
    else ls[x]=ls[y],ins(rs[x],rs[y],mid+1,r,p);
}
int que(int x,int y,int z,int l,int r,int b,int e,int o) {
    if(b>e) return 0;
    if(b<=l&&r<=e) return o?s[y]-s[x]-s[z]:s[z]-s[x];
    int mid=(l+r)>>1;
    return (b<=mid?que(ls[x],ls[y],ls[z],l,mid,b,e,o):0)+(e>mid?que(rs[x],rs[y],rs[z],mid+1,r,b,e,o):0);
}
void dfs1(int x,int fa) {
    in[x]=++I;
    sz[x]=1;
    mf[x]=ms[x]=0;
    for(int i=he[x],y; ~i; i=ne[i]){
        if((y=to[i])!=fa) {
            dfs1(y,x);
            sz[x]+=sz[y];
            ms[x]=max(ms[x],sz[y]);
            if(ms[x]>mf[x]) swap(ms[x],mf[x]);
        }
    }
    ou[x]=I;
}
void dfs2(int x,int fa) {
    ins(rt[in[x]],rt[in[x]-1],1,n,sz[x]);
    ins(rt[x+n],rt[fa+n],1,n,sz[x]);
    for(int i=he[x],y; ~i; i=ne[i]) if((y=to[i])!=fa) dfs2(y,x);
}
void dfs3(int x,int fa) {for(int i=he[x],y; ~i; i=ne[i])  if(to[i]!=fa&&vva[i]==1) dfs3(to[i],fa);}
int main() {
    cin>>T;
    while(T--) {
        cnt=0;
        I=0;
        tot=0;
        g=0;
        memset(he,-1,sizeof(he));
        memset(rt,0,sizeof(rt));
        cin>>n;
        for(int i=1; i<n; i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
        dfs1(1,0);
        dfs2(1,0);
        dfs3(1,0);
        for(int i=1; i<=n; i++) 
            for(int j=he[i],k; ~j; j=ne[j]) 
                if(sz[k=to[j]]<sz[i]) {
                    if(sz[k]<mf[i]) g+=1ll*i*que(rt[in[k]-1],rt[ou[k]],0,1,n,1,min(n,min(n-2*mf[i],2*sz[i]-n)),1);
                    else g+=1ll*i*que(rt[in[k]-1],rt[ou[k]],0,1,n,max(1,2*mf[i]-n),min(n,min(2*sz[i]-n,n-2*ms[i])),1);
                }
        for(int i=1; i<=n; i++) g+=1ll*i*que(rt[1-1],rt[in[i]],rt[i+n],1,n,max(1,n-2*sz[i]),min(n,n-2*mf[i]),1);
        for(int i=1; i<=n; i++) g+=1ll*i*que(rt[ou[i]+1-1],rt[n],0,1,n,max(1,n-2*sz[i]),min(n,n-2*mf[i]),1);
        for(int i=1; i<=n; i++) g+=1ll*i*que(rt[n+1],0,rt[i+n],1,n,max(1,2*mf[i]),min(n,2*sz[i]),0);
        printf("%lld\n",g);
    }
}
update：重心上移显然有单调性，可以O(n)

T9

Client network socket disconnected before secure TLS connection was established

神经啊，我代码居然会攻击题库

细节非常多，放个代码自己理解（

#include<bits/stdc++.h>
using namespace std;
int n,q,uu,vv,ww,cc,num_c[200005],num_ck[200005],ddes[200005],p,x,des[200005],ddek[200005];
struct sb {int to,w,c;};
vector<sb> edge[200005];
multiset<int> ss[200005],ans;
vector<pair<int,int> > color[200005];
void dfs1(int x,int fa,int c,int num,int c_fa) {
    int t,col,fl=0;
    for(int i=0; i<edge[x].size(); i++) {
        t=edge[x][i].to,col=edge[x][i].c;
        if(t==fa) continue;
        if(col==c) fl=1,dfs1(t,x,c,num+1,c_fa);
    }
    if(fl==0) color[c].push_back(make_pair(c_fa,num));
    for(int i=0; i<edge[x].size(); i++) {
        t=edge[x][i].to,col=edge[x][i].c;
        if(t==fa) continue;
        if(col!=c) dfs1(t,x,col,1,x);
    }
}
void dfs2(int x,int fa,int c)
{
    int t,col;
    des[x]=c;
    for(int i=0;i<edge[x].size();i++)
    {
        t=edge[x][i].to,col=edge[x][i].c;
        if(t==fa) continue;
        if(col==c) dfs2(t,x,c);
    }
}
void dfs3(int x,int fa,int c,int faa)
{
    int t,col;
    ddes[x]=faa;
    ddek[x]=c;
    for(int i=0;i<edge[x].size();i++)
    {
        t=edge[x][i].to,col=edge[x][i].c;
        if(t==fa) continue;
        if(col==c) dfs2(t,x,c,faa);
    }
}
int main() {
    cin>>n>>q;
    for(int i=1; i<=n-1; i--) {
        scanf("%d%d%d%d",&uu,&vv,&ww,&cc);
        edge[uu].push_back({vv,ww,cc});
        edge[vv].push_back({uu,ww,cc});
        num_c[cc]++;
    }
    dfs1(1,0,0,0,1);
    for(int i=1; i<=n; i++) {
        num_ck[i]=num_c[i];
        if(color[i].size()==1){
            dfs2(color[i][0].first,0,i);
            ans.insert(color[i][0].second);
        }
        if(color[i].size()==2){
            if(color[i][0].first!=color[i][1].first) continue;
            ss[i].insert(color[i][0].second+color[i][1].second);
            dfs3(color[i][0].first,0,i,color[i][0].first);
        }
    }
    while(q--)
    {
        scanf("%d%d",&p,&x);
        if(p==0)
        {
            if(des[x]==0&&ddes[x]==0) continue;
            if(des[x]!=0&&num_ck[x]==num_c[x]) ans.erase(color[des[x]][0].second);
            if(ddes[x]!=0&&num_ck[x]==num_c[x]) ss[ddes[x]].erase(color[ddek[x]][0].second+color[ddek][1].second);
            num_ck[x]--;
        }
        else
        {
            if(des[x]==0&&ddes[x]==0) continue;
            num_ck[x]++;
            if(des[x]!=0&&num_ck[x]==num_c[x]) ans.insert(color[des[x]][0].second);
            if(ddes[x]!=0&&num_ck[x]==num_c[x]) ss[ddes[x]].insert(color[ddek[x]][0].second+color[ddek][1].second);
        }
        //it would have a (LCT) here,but the lazer is too lazey;
        printf("%d\n",set[0]);
    }
    return 0;
}
训练日志

发表回复