大连微信网站开发,wordpress 文章左右分栏,网站底部样式,网站备案号 有效期和BZOJ消耗站一样#xff0c;先将那个询问的简图构建出来#xff0c;然后就是简单的树形DP。 #xff08;倍增数组开小了#xff0c;然后就狂WA#xff0c;自己生成的极限数据深度又没有那么高#xff0c;链又奇迹般正确#xff09; 1 #include cstdio2 #includ… 和BZOJ消耗站一样先将那个询问的简图构建出来然后就是简单的树形DP。 倍增数组开小了然后就狂WA自己生成的极限数据深度又没有那么高链又奇迹般正确 1 #include cstdio2 #include cstring3 #include vector4 #include algorithm5 #define min(a,b) ((a)(b)?(a):(b))6 #define max(a,b) ((a)(b)?(a):(b))7 #define oo 0x3f3f3f3f3f3f3f3f8 #define N 10000109 #define P 1910 using namespace std;11 12 typedef long long dnt;13 14 int n, m;15 vectorint g[N];16 int dfn[N], anc[N][P1], dep[N], idc;17 int head[N], ikey[N], dest[NN], next[NN], etot;18 dnt dp[N][4]; 19 int qcnt, aa[N], stk[N], top;20 dnt ans[3];21 22 void adde( int u, int v ) {23 etot;24 next[etot] head[u];25 dest[etot] v;26 head[u] etot;27 }28 void dfs( int u ) {29 dfn[u] idc;30 for( int p1; pP; p )31 anc[u][p] anc[anc[u][p-1]][p-1];32 for( int t0; tg[u].size(); t ) {33 int vg[u][t];34 if( vanc[u][0] ) continue;35 anc[v][0] u;36 dep[v] dep[u]1;37 dfs(v);38 }39 }40 bool cmp( int u, int v ) {41 return dfn[u]dfn[v];42 }43 int lca( int u, int v ) {44 if( dep[u]dep[v] ) swap(u,v);45 int tdep[u]-dep[v];46 for( int p0; t; t1,p )47 if( t1 ) uanc[u][p];48 if( uv ) return u;49 for( int pP; p0 anc[u][0]!anc[v][0]; p-- )50 if( anc[u][p]!anc[v][p] ) uanc[u][p], vanc[v][p];51 return anc[u][0];52 }53 void build() {54 stk[top1] 1;55 head[1] 0;56 57 sort( aa1, aa1qcnt, cmp );58 59 etot 0;60 for( int i2-(aa[1]!1); iqcnt; i ) {61 int calca(aa[i],stk[top]);62 while( dep[ca]dep[stk[top]] ) {63 int u;64 u stk[top--];65 if( dep[ca]dep[stk[top]] ) {66 if( ca!stk[top] ) {67 stk[top] ca;68 head[ca] 0;69 }70 adde( stk[top], u );71 break;72 } 73 adde( stk[top], u );74 }75 stk[top] aa[i];76 head[aa[i]] 0;77 }78 for( int itop; i2; i-- )79 adde( stk[i-1], stk[i] );80 }81 dnt sml, big, sum, cnt;82 void dodp( int u ) {83 if( ikey[u] ) {84 dp[u][0] 0;85 dp[u][1] 0;86 dp[u][2] 1;87 dp[u][3] 0;88 } else {89 dp[u][0] oo;90 dp[u][1] -oo;91 dp[u][2] 0;92 dp[u][3] 0;93 }94 for( int thead[u]; t; tnext[t] ) {95 int vdest[t]; 96 dnt wdep[v]-dep[u];97 dodp(v);98 dp[u][0] min( dp[u][0], dp[v][0]w );99 dp[u][1] max( dp[u][1], dp[v][1]w );
100 dp[u][2] dp[v][2];
101 dp[u][3] dp[v][3]w*dp[v][2];
102 }
103 if( ikey[u] ) {
104 sml 0;
105 big 0;
106 sum 0;
107 cnt 1;
108 } else {
109 sml oo;
110 big -oo;
111 sum 0;
112 cnt 0;
113 }
114 for( int thead[u]; t; tnext[t] ) {
115 int vdest[t];
116 dnt wdep[v]-dep[u];
117 ans[0] min( ans[0], smlwdp[v][0] );
118 ans[1] max( ans[1], bigwdp[v][1] );
119 ans[2] cnt*(dp[v][3]w*dp[v][2]) sum*dp[v][2];
120 sml min( sml, dp[v][0]w );
121 big max( big, dp[v][1]w );
122 cnt dp[v][2];
123 sum dp[v][3]w*dp[v][2];
124 }
125 }
126 int main() {
127 scanf( %d, n );
128 for( int i1,u,v; in; i ) {
129 scanf( %d%d, u, v );
130 g[u].push_back( v );
131 g[v].push_back( u );
132 }
133 anc[1][0] 1;
134 dep[1] 0;
135 dfs(1);
136 scanf( %d, m );
137 for( int i1; im; i ) {
138 scanf( %d, qcnt );
139 for( int j1; jqcnt; j )
140 scanf( %d, aaj );
141
142 if( qcnt1 ) {
143 printf( 0 0 0\n );
144 continue;
145 }
146
147 build();
148
149 for( int j1; jqcnt; j )
150 ikey[aa[j]] 1;
151 ans[0] oo;
152 ans[1] 0;
153 ans[2] 0;
154 dodp(1);
155 for( int j1; jqcnt; j )
156 ikey[aa[j]] 0;
157
158 printf( %lld %lld %lld\n, ans[2], ans[0], ans[1] );
159 }
160 } View Code 转载于:https://www.cnblogs.com/idy002/p/4394525.html
