#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MEM(a,b) memset(a,(b),sizeof(a)) #define MAX(a,b) ((a) > (b) ? (a) : (b)) #define MIN(a,b) ((a) < (b) ? (a) : (b)) #define MP make_pair #define pb push_back #define inf 1000000000 #define maxn 500000 #define maxl 19 typedef vector vi; typedef pair pi; typedef long long LL; vi E[maxn+5]; int L[maxn+5],P[maxl][maxn+5],n; int visited=0; LL C[maxn+5],S[maxn+5]; int start[maxn+5],finish[maxn+5],now; void dfs1(int u,int p) { L[u] = p!=-1 ? L[p]+1 : 1; P[0][u]= p ; start[u]=++now; // discovered time for(int j=1;jfinish[a]) return true; return false; } void dfs2(int u,int p) // updates the value of each edge { for(int i=0;i= 0; i--) if (L[p] - (1 << i) >= L[q]) p = P[i][p]; if (p == q) return p; for (i = log; i >= 0; i--) if (P[i][p] != -1 && P[i][p] != P[i][q]) p = P[i][p], q = P[i][q]; return P[0][p]; } pi getCommonPath(int u,int a,int v,int b) // common path between u->a and v->b { if(!isAncestor(v,a)) return MP(0,0); // v has to be an ancestor of a to have any common path int x=lca(a,b); if(L[v]x is the common path } else // u is an ancestor of v, so the beginning of common path should be from v { if(isAncestor(v,x)) // if v is not an ancestor of x no common path exists return MP(v,x);// v->x is the common path } return MP(0,0); } int main() { int i,j,k,m1,m2; scanf("%d%d%d",&n,&m1,&m2); assert(n>=1 && n<=maxn/5 && m1>=1 && m1<=maxn && m2>=1 && m2<=maxn); for(i=1;iq is the common path, edges on that should be decreased by 1 since they were increased before X=getCommonPath(u,a,v,c); C[X.second]--; C[X.first]++; X=getCommonPath(u,a,v,d); C[X.second]--; C[X.first]++; X=getCommonPath(u,b,v,c); C[X.second]--; C[X.first]++; X=getCommonPath(u,b,v,d); C[X.second]--; C[X.first]++; } dfs2(1,-1); dfs3(1,-1); for(i=0;i