LOJ P10131 暗的连锁题解

每日一题 day27 打卡
Analysis

对于每条非树边 , 覆盖
时间复杂度
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define int long long
  6 #define maxn 100000+10
  7 using namespace std;
  8 inline int read() 
  9 {
 10     int x=0;
 11     bool f=1;
 12     char c=getchar();
 13     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
 14     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
 15     if(f) return x;
 16     return 0-x;
 17 }
 18 inline void write(int x)
 19 {
 20     if(x<0){putchar('-');x=-x;}
 21     if(x>9)write(x/10);
 22     putchar(x%10+'0');
 23 }
 24 int n,m,cnt;
 25 int head[2*maxn],dep[maxn],sum[2*maxn],c[2*maxn];
 26 int dp[maxn][25];
 27 struct node
 28 {
 29     int v,nex;
 30 }edge[2*maxn];
 31 inline void print(int x)
 32 {
 33     write(x);
 34     printf("
");
 35 }
 36 inline void add(int x,int y)
 37 {
 38     edge[++cnt].v=y;
 39     edge[cnt].nex=head[x];
 40     head[x]=cnt;
 41 }
 42 inline void init(int from,int fa)
 43 {
 44     dep[from]=dep[fa]+1;
 45     for(int i=1;i<=20;i++) 
 46         dp[from][i]=dp[dp[from][i-1]][i-1];
 47     for(int i=head[from];i;i=edge[i].nex)
 48     {
 49         int to=edge[i].v;
 50         if(to==fa) continue;
 51         dp[to][0]=from;
 52         init(to,from);
 53     }
 54 }
 55 inline int lca(int x,int y)
 56 {
 57     if(dep[x]<dep[y]) swap(x,y);
 58     for(int i=20;i>=0;i--)
 59     {
 60         if(dep[dp[x][i]]>=dep[y]) x=dp[x][i];
 61         if(x==y) return x;
 62     }
 63     for(int i=20;i>=0;i--)
 64         if(dp[x][i]!=dp[y][i])
 65         {
 66             x=dp[x][i];
 67             y=dp[y][i];
 68         }
 69     return dp[x][0];
 70 }
 71 inline void dfs(int from,int fa)
 72 {
 73     for(int i=head[from];i;i=edge[i].nex)
 74     {
 75         int to=edge[i].v;
 76         if(to==fa) continue;
 77         dfs(to,from);
 78         sum[from]+=sum[to];
 79     }
 80 }
 81 signed main()
 82 {
 83     n=read();m=read();
 84     for(int i=1;i<=n-1;i++)
 85     {
 86         int x=read(),y=read();
 87         add(x,y);add(y,x);
 88     }
 89     init(1,0);
 90     for(int i=1;i<=m;i++)
 91     {
 92         int x=read(),y=read();
 93         sum[x]++,sum[y]++,sum[lca(x,y)]-=2;
 94     }
 95     dfs(1,0);
 96     int ans=0;
 97     for(int i=2;i<=n;i++)
 98     {
 99         if(sum[i]==0) ans+=m;
100         if(sum[i]==1) ans++;
101     }
102     print(ans);
103     return 0;
104 }
请各位大佬斧正~~（反正我不认识斧正是什么意思）~~
LOJ P10131 暗的连锁 题解

Analysis

LOJ P10131 暗的连锁题解
