思考题 for everyone

Man on Graph

Given a graph of N nodes and M edges. On node i there are A_i men. Then each person moves along 1 edge randomly connected to the node he stands. But if two men walked along the same edge, they'll fight and both die.
Given q queries:
1. "1 x y" set the number of people in X to be Y
2. "2" find the expected number of people left after moving.
Proceed the queries.
Test 1(8%) - the graph is a tree,A_i=1,q=1,N=1000,M=1000
Test 2(8%) - the graph is a tree,A_i=1,q=1,N=1e5,M=1e5
Test 3(8%) - the graph is a tree,q=1,N=1e5,M=1e5
Test 4(8%) - the graph is a tree,A_i=1,N=1e5,M=1e5,q=1e5
Test 5(8%) - the graph is a tree,N=1000,M=1000,q=1000
Test 6(10%) - the graph is a tree,N=1e5,M=1e5,q=1e5
Test 7(8%) - A_i=1,q=1,N=1000,M=1000
Test 8(8%) - A_i=1,q=1,N=1e5,M=1e5
Test 9(8%) - q=1,N=1e5,M=1e5
Test 10(8%) - A_i=1,N=1e5,M=1e5,q=1e5
Test 11(8%) - N=1000,M=1000,q=1000
Test 12(10%) - N=1e5,M=1e5,q=1e5
Orange boy come and AC quickly