Submission #5406519

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//2019.5.15 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-10
#define RG register
inline int read() {
    res s=0,ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s;
}
inline LL Read() {
    RG LL s=0;
    res ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

//2019.5.15 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-10
#define RG register
inline int read() {
    res s=0,ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s;
}
inline LL Read() {
    RG LL s=0;
    res ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s;
}
inline void swap(res &x,res &y) {
    x^=y^=x^=y;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=2e3+10;
namespace MAIN {
    typedef vector<int> vec;
#define pb push_back
    typedef pair<int,int> Pair;
#define fi first
#define se second
#define mp make_pair
    int n,m;
    struct E{
        int next,to;
        E() {}
        E(res next,res to):next(next),to(to) {}
    }edge[N<<1];
    int head[N],cnt;
    inline void addedge(const res &u,const res &v){
        edge[++cnt]=E(head[u],v),head[u]=cnt;
        edge[++cnt]=E(head[v],u),head[v]=cnt;
    }
    int fa[N][N],dep[N][N];
    bool vis[N][N];
    void dfs(res x,res fax,res depx,const res &rt){
        fa[rt][x]=fax,dep[rt][x]=depx;
        for(res i=head[x];~i;i=edge[i].next){
            res tox=edge[i].to;
            if(tox==fax)continue;
            dfs(tox,x,depx+1,rt);
        }
    }
    set<int> S[N];
    vec getlj(res x,res y){
        RG vec ret;
        ret.clear();
        while(x!=y)ret.pb(x),x=fa[y][x];
        ret.pb(y);
        return ret;
    }
    inline void tj(const res &x,const res &y){
        vis[x][y]=vis[y][x]=1,S[x].insert(y),S[y].insert(x);
    }
    inline void sc(const res &x,const res &y){
        vis[x][y]=vis[y][x]=0,S[x].erase(y),S[y].erase(x);
    }
    void add(res x,res y){
        if(vis[x][y])return;
        RG vec lj=getlj(x,y);
        res sz=int(lj.size())-1,s=x,t=y,id=0;
        for(res i=0;i<sz;i++)if(vis[s][lj[i]])s=lj[i],id=i;
        for(res i=sz-1;i>=id;i--)if(vis[t][lj[i]])t=lj[i];
        if(t==x||vis[s][t])return;
        RG vector<Pair> E;
        lj.clear();
        for(auto i:S[s])if(dep[s][i]==dep[s][t]+dep[t][i])E.pb(mp(t,i)),lj.pb(i);
        for(auto i:lj)sc(i,s);
        lj.clear();
        for(auto i:S[t])if(dep[t][i]==dep[t][s]+dep[s][i])E.pb(mp(s,i)),lj.pb(i);
        for(auto i:lj)sc(i,t);
        tj(s,t);
        for(auto i:E)add(i.fi,i.se);
    }
    bool g[N][N];
    void dfs(res x,const res &rt){
        g[rt][x]=1;
        for(auto i:S[x]){
            if(g[rt][i])continue;
            if(dep[i][rt]==dep[i][x]+dep[x][rt])dfs(i,rt);
        }
    }
    int ans;
    inline void MAIN(){
        n=read(),m=read();
        for(res i=1;i<=n;i++)head[i]=-1;
        for(res i=1;i<n;i++){
            res u=read(),v=read();
            addedge(u,v);
        }
        for(res i=1;i<=n;i++)dfs(i,0,0,i);
        for(res i=1;i<=m;i++){
            res u=read(),v=read();
            add(u,v);
        }
        for(res i=1;i<=n;i++){
            dfs(i,i);
            for(res j=i+1;j<=n;j++)if(g[i][j])ans++;
        }
        printf("%d\n",ans);
    }
}
int main() {
//    srand((unsigned)time(NULL));
//    freopen("graph.in","r",stdin);
//    freopen("graph.out","w",stdout);
    MAIN::MAIN();
    return 0;
}

Submission Info

Judge Result