有前景的网站建设,地方门户网站如何推广,佛山企业一般在哪网站发布消息,wordpress 防注册题目链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid2586 这题以前做过…现在用tarjan搞一发…竟然比以前暴力过的慢………… 由于是离线算法#xff0c;需要Query来保存查询数据#xff0c;Ans来保存结果。最后输出的时候按照idx的顺序输出#xff0c;所以胡搞…题目链接http://acm.hdu.edu.cn/showproblem.php?pid2586 这题以前做过…现在用tarjan搞一发…竟然比以前暴力过的慢………… 由于是离线算法需要Query来保存查询数据Ans来保存结果。最后输出的时候按照idx的顺序输出所以胡搞了个排序。。 dfs每次更新depth当前点depth是上一个点累积下来的。 1 /*2 ━━━━━┒ギリギリ♂ eye3 ┓┏┓┏┓┃キリキリ♂ mind4 ┛┗┛┗┛┃○5 ┓┏┓┏┓┃ /6 ┛┗┛┗┛┃ノ)7 ┓┏┓┏┓┃8 ┛┗┛┗┛┃9 ┓┏┓┏┓┃10 ┛┗┛┗┛┃11 ┓┏┓┏┓┃12 ┛┗┛┗┛┃13 ┓┏┓┏┓┃14 ┃┃┃┃┃┃15 ┻┻┻┻┻┻16 */17 #include algorithm18 #include iostream19 #include iomanip20 #include cstring21 #include climits22 #include complex23 #include fstream24 #include cassert25 #include cstdio26 #include bitset27 #include vector28 #include deque29 #include queue30 #include stack31 #include ctime32 #include set33 #include map34 #include cmath35 36 using namespace std;37 38 #define fr first39 #define sc second40 #define cl clear41 #define BUG puts(here!!!)42 #define W(a) while(a--)43 #define pb(a) push_back(a)44 #define Rint(a) scanf(%d, a)45 #define Rll(a) scanf(%lld, a)46 #define Rs(a) scanf(%s, a)47 #define Cin(a) cin a48 #define FRead() freopen(in, r, stdin)49 #define FWrite() freopen(out, w, stdout)50 #define Rep(i, len) for(int i 0; i (len); i)51 #define For(i, a, len) for(int i (a); i (len); i)52 #define Cls(a) memset((a), 0, sizeof(a))53 #define Clr(a, x) memset((a), (x), sizeof(a))54 #define Full(a) memset((a), 0x7f7f, sizeof(a))55 #define lrt rt 156 #define rrt rt 1 | 157 #define pi 3.1415926535958 #define RT return59 typedef long long LL;60 typedef long double LD;61 typedef unsigned long long ULL;62 typedef pairint, int pii;63 typedef pairstring, int psi;64 typedef mapstring, int msi;65 typedef vectorLL vl;66 typedef vectorvl vvl;67 typedef vectorbool vb;68 69 typedef struct Query {70 int idx;71 int u, v;72 Query() {}73 Query(int uu, int vv, int ii) : u(uu), v(vv), idx(ii) {}74 }Query;75 76 typedef struct Edge {77 int v, w;78 Edge() {}79 Edge(int vv, int ww) : v(vv), w(ww) {}80 }Edge;81 82 typedef struct Ans {83 int idx;84 int ans;85 Ans() {}86 Ans(int aa, int ii) :ans(aa), idx(ii) {}87 }Ans;88 89 const int maxn 40010;90 const int maxm 222;91 int n, m, qcnt, acnt;92 int depth[maxn];93 int in[maxn];94 bool vis[maxn];95 int pre[maxn];96 Query q[maxm];97 Ans ans[maxn];98 vectorEdge G[maxn];99 int u, v, w;
100
101 int find(int x) {
102 return x pre[x] ? x : pre[x] find(pre[x]);
103 }
104
105 void unite(int x, int y) {
106 x find(x);
107 y find(y);
108 if(x ! y) pre[y] x;
109 }
110
111 void dfs(int u, int d) {
112 // pre[u] u;
113 depth[u] d;
114 Rep(i, G[u].size()) {
115 int v G[u][i].v;
116 if(!vis[v]) {
117 dfs(v, dG[u][i].w);
118 unite(u, v);
119 }
120 }
121 vis[u] 1;
122 Rep(i, qcnt) {
123 int uu q[i].u;
124 int vv q[i].v;
125 int idx q[i].idx;
126 if(vis[uu] vv u) {
127 ans[acnt].idx idx;
128 ans[acnt].ans abs(depth[vv] - depth[uu]);
129 }
130 if(vis[vv] uu u) {
131 ans[acnt].idx idx;
132 ans[acnt].ans abs(depth[uu] - depth[vv]);
133 }
134 }
135 }
136
137 bool cmp(Ans x, Ans y) {
138 return x.idx y.idx;
139 }
140
141 int main() {
142 // FRead();
143 int T;
144 Rint(T);
145 W(T) {
146 Rint(n); Rint(m);
147 Cls(vis); Cls(depth); Cls(ans); Cls(G);
148 acnt qcnt 0; Rep(i, n5) G[i].cl(), pre[i] i;
149 Rep(i, n-1) {
150 Rint(u); Rint(v); Rint(w);
151 G[u].push_back(Edge(v, w));
152 in[v];
153 }
154 Rep(i, m) {
155 Rint(u); Rint(v);
156 q[qcnt] Query(u, v, i);
157 }
158 For(i, 1, n1) if(in[i] 0) dfs(i, 0);
159 sort(ans, ansacnt, cmp);
160 Rep(i, acnt) {
161 printf(%d\n, ans[i].ans);
162 }
163 }
164 RT 0;
165 } 转载于:https://www.cnblogs.com/kirai/p/5513617.html
