[poj3417]Network(LCA+树形dp)

 ?1 //#pragma comment(linker, "/STACK:1024000000,1024000000") ?2 #include<cstdio> ?3 #include<cstring> ?4 #include<algorithm> ?5 #include<cstdlib> ?6 #include<cmath> ?7 #include<iostream> ?8 #include<vector> ?9 typedef long long ll; 10 using namespace std; ??11 const int maxn=101000; ?12 const int maxm=30; ??13 int _pow[maxm],m,n; ??14 int head[maxn],tot; 15 int ver[maxn*2],depth[maxn*2],first[maxn],rmq[maxn*2][25],id;//5个数组，注意哪个需要乘2 ?16 int pre[maxn],val[maxn]; 17 int ans; 18 inline int read(){ 19 ????char k=0;char ls;ls=getchar();for(;ls<‘0‘||ls>‘9‘;k=ls,ls=getchar()); 20 ????int x=0;for(;ls>=‘0‘&&ls<=‘9‘;ls=getchar())x=(x<<3)+(x<<1)+ls-‘0‘; 21 ????if(k==‘-‘)x=0-x;return x; 22 } 23 ?24 struct edge{ 25 ????int to,nxt; ??26 }e[maxn*2];//链式前向星建树 ?27 ?28 void init(){ 29 ????memset(head,-1,sizeof head); ?30 ????tot=0; 31 ????id=0; 32 ????ans=0; 33 } 34 ?35 void add_edge(int u,int v){ ??36 ????e[tot].to=v; 37 ????e[tot].nxt=head[u]; 38 ????head[u]=tot++; 39 } 40 ???41 void dfs(int u,int fa,int dep){ 42 ????ver[++id]=u;//第i个访问到的结点编号 ?43 ????depth[id]=dep;//第i个访问到的结点深度 ??44 ????first[u]=id; 45 ????for(int i=head[u];i!=-1;i=e[i].nxt){ 46 ????????int v=e[i].to; 47 ????????if(v==fa) continue; 48 ????????//pre[v]=u; 49 ????????dfs(v,u,dep+1); 50 ????????ver[++id]=u;//后序遍历，再次访问父节点 ?51 ????????depth[id]=dep; 52 ????} 53 } 54 ?55 void rmq_init(int n){ 56 ????int k=int(log(n)/log(2)); 57 ????for(int i=1;i<=n;++i) ???rmq[i][0]=i; ??58 ????for(int j=1;j<=k;++j){ ??59 ????????for(int i=1;i+_pow[j]-1<=n;++i){//因为存的是索引 ?60 ????????????int a=rmq[i][j-1],b=rmq[i+_pow[j-1]][j-1]; ??61 ????????????rmq[i][j]=depth[a]<depth[b]?a:b; 62 ????????} 63 ????} 64 } 65 ???66 int rmq_query(int l,int r){ 67 ????int k=int(log(r-l+1.0)/log(2.0)); ??68 ????int a=rmq[l][k],b=rmq[r-_pow[k]+1][k]; ??69 ????return depth[a]<depth[b]?a:b; 70 }//返回的依然是索引 ?71 ???72 int LCA(int u,int v){ 73 ????int x=first[u],y=first[v]; ??74 ????if(x>y)swap(x,y); ??75 ????int res=rmq_query(x,y); ??76 ????return ver[res]; ?77 } 78 void dfs(int u,int fa){ 79 ????for(int i=head[u];i!=-1;i=e[i].nxt){ 80 ????????int v=e[i].to; 81 ????????if(v==fa) continue; 82 ????????dfs(v,u); 83 ????????val[u]+=val[v]; 84 ????} 85 ????if(val[u]==1) ans++; 86 ????else if(!val[u]&&u!=1) ans+=m; 87 } 88 ?89 int main(){ 90 ????for(int i=0;i<maxm;++i) ???_pow[i]=1<<i; //预处理2^n ?91 ????int k,a,b; 92 ????n=read();m=read(); 93 ????init(); 94 ????//for(int i=1;i<=n;i++) val[i]=read(); 95 ????for(int i=0;i<n-1;++i){ 96 ????????a=read(),b=read(); 97 ????????add_edge(a,b); 98 ????????add_edge(b,a); 99 ????}100 ????dfs(1,-1,0);101 ????rmq_init(2*n-1);102 ????for(int i=0;i<m;++i){103 ????????a=read();b=read();104 ????????val[a]++,val[b]++,val[LCA(a,b)]-=2;105 ????}106 ????dfs(1,-1);107 ????printf("%d\n",ans);108 ????109 ????return 0;110 }