网站首页菜单栏,网站服务器的重要性,自己做的网站怎么链接火车头采集,建立网站的基本条件题意#xff1a;BaoBao正在进行在线考试#xff08;都是选择题#xff09;#xff0c;每个题都有唯一的一个正确答案#xff0c;但是考试系统有m个bug(就是有m个限制)#xff0c;每个bug表示为第u个问题和第v个问题你必须选择相同的选项#xff0c;题目问你#xff0c;…题意BaoBao正在进行在线考试都是选择题每个题都有唯一的一个正确答案但是考试系统有m个bug(就是有m个限制)每个bug表示为第u个问题和第v个问题你必须选择相同的选项题目问你如果你修好了第i个bugBaoBao最高可以取得多少分。 题目数量1e5BUG数量1e5(真多)答案范围1e5 思路首先如果出现了bug导致{a1,a2,...,an}n个题目必须选择一样的结果那么最高得分肯定是众数的出现次数。我们发现bug是具有传递性的如果bug连成了一个环而且你只修复其中一个bug那么这个bug的修复是对整个考试系统是没有任何影响的所以我们不需要考虑这个环内的边然后我们可以把这些环抠出来缩成一个点具体的缩点方法很多也可以把整个块拉成一条链或者拓扑排序弄一弄或者tarjan缩一下我是用tarjan缩点的这样整个图就是一个树了。现在修一个bug就相当于断了一条边一棵树就被切成两半了我们需要同时得到两边的众数的个数是多少这时候就有一个算法叫dsu on tree了这是一个复杂度十分科学的暴力算法http://codeforces.com/problemset/problem/600/E 这个题是一个dsu on tree的裸题就是让你求每个子树的众数不会这个算法的可以去学一下做完这个题你就发现你会做子树内众数的个数了现在还有个问题子树外的怎么求呢我们可以反过来做一开始把所有的节点加进贡献里面去然后dsu on tree的时候询问子树众数的添加删除的时候我们只要做相反的操作就行了。 具体细节还挺多的。 1 #includebits/stdc.h2 using namespace std;3 const int maxn 100010;struct Edge {4 int to,next,id;5 Edge(int _to0,int _next-1,int _id0):to(_to),next(_next),id(_id) {};6 } edge[maxn*2];7 int head[maxn],etot;8 inline void addedge(int u,int v,int id) {9 edge[etot]Edge(v,head[u],id);10 head[u]etot;11 }12 vectorint nodes[maxn];13 int Cnt;14 int dfn[maxn],low[maxn],tot;15 bool Vis[maxn];16 int S[maxn],top;17 int id[maxn];18 void tarjan(int x,int fa) {19 low[x]dfn[x]tot;20 S[top]x;21 Vis[x]1;22 for(register int ihead[x]; ~i; iedge[i].next) {23 int vedge[i].to;24 if(vfa) {fa0;continue;}25 if(!dfn[v]) {26 tarjan(v,x);27 low[x]min(low[x],low[v]);28 } else if(Vis[v])29 low[x]min(low[x],dfn[v]);30 }31 if(low[x]dfn[x]) {32 Cnt;33 while(1) {34 int nowS[top--];35 Vis[now]0;36 id[now]Cnt;37 nodes[Cnt].push_back(now);38 if(nowx) break;39 }40 }41 }42 int a[maxn],ans[maxn];43 vectorintv[maxn];44 vectorintedg[maxn],eid[maxn];45 int summ;46 bool vis[maxn];47 int sz[maxn],son[maxn];48 vectorintvv;49 int getid(int x) {50 return lower_bound(vv.begin(),vv.end(),x)-vv.begin()1;51 }52 void init(int now,int pre-1){53 vis[now]1;54 sz[now]v[now].size();55 for(int it:v[now])vv.push_back(a[it]);56 for(int to:edg[now]){57 if(topre)continue;58 init(to,now);59 sz[now]sz[to];60 if(!son[now]||sz[to]sz[son[now]])61 son[now]to;62 }63 }64 int tp[maxn],tp2[maxn],cnt[maxn],cnt2[maxn],Max0,Max20;65 bool big[maxn];66 void update(int nows,int pre,int val){67 for(int now:v[nows]){68 tp[cnt[a[now]]]--;69 cnt[a[now]]val;70 tp[cnt[a[now]]];71 if(cnt[a[now]]Max)72 Maxcnt[a[now]];73 if(!tp[Max])Max--;74 tp2[cnt2[a[now]]]--;75 cnt2[a[now]]-val;76 tp2[cnt2[a[now]]];77 if(cnt2[a[now]]Max2)78 Max2cnt2[a[now]];79 if(!tp2[Max2])Max2--;80 }81 for(int to:edg[nows])82 if(to!prebig[to]0)83 update(to,nows,val);84 }85 void update2(int nows,int pre,int val){86 for(int now:v[nows]){87 tp2[cnt2[a[now]]]--;88 cnt2[a[now]]val;89 tp2[cnt2[a[now]]];90 if(cnt2[a[now]]Max2)91 Max2cnt2[a[now]];92 if(!tp2[Max2])Max2--;93 }94 }95 int temp;96 void dfs(int now,int pre-1,int kep0,int id0){97 int tid0;98 for(register int i0;iedg[now].size();i){99 int toedg[now][i];
100 if(toson[now])tideid[now][i];
101 if(topre||toson[now])continue;
102 dfs(to,now,0,eid[now][i]);
103 }
104 if(son[now])
105 dfs(son[now],now,1,tid),big[son[now]]1;
106 update(now,pre,1);
107 ans[id]MaxMax2-temp;
108 big[son[now]]0;
109 if(!kep)update(now,pre,-1);
110 }
111 void init2(int now,int pre-1){
112 for(int it:v[now])a[it]getid(a[it]);
113 update2(now,0,1);
114 for(int to:edg[now]){
115 if(topre)continue;
116 init2(to,now);
117 }
118 }
119 void solve(int now){
120 vv.clear();
121 init(now);
122 for(register int i0;isz[now];i)tp[i]tp2[i]cnt[i]cnt2[i]big[i]0;MaxMax20;
123 sort(vv.begin(),vv.end());
124 vv.erase(unique(vv.begin(),vv.end()),vv.end());
125 init2(now);
126 summMax2;
127 tempMax2;
128 dfs(now);
129 }
130 int main()
131 {
132 int T;
133 scanf(%d,T);
134 while(T--){
135 int n,m;
136 scanf(%d%d,n,m);
137 for(register int i1;in;i)head[i]-1,dfn[i]son[i]vis[i]Vis[i]0,v[i].clear(),edg[i].clear(),eid[i].clear();
138 etottotCnttop0;
139 for(register int i1;in;i)scanf(%d,ai);
140 for(register int i1;im;i){
141 int u,v;
142 scanf(%d%d,u,v);
143 addedge(v,u,i);
144 addedge(u,v,i);
145 }
146 for(register int i1;in;i)if(!dfn[i])tarjan(i,0);
147 for(register int i1;in;i)v[id[i]].push_back(i);
148 summ0;
149 for(register int i1;in;i){
150 for(register int jhead[i];~j;jedge[j].next){
151 int uid[i],toid[edge[j].to];
152 if(uto){
153 ans[edge[j].id]0;
154 continue;
155 }
156 edg[u].push_back(to);eid[u].push_back(edge[j].id);
157 }
158 }
159 for(register int i1;iCnt;i)
160 if(!vis[i])
161 solve(i);
162 for(register int i1;im;i){
163 if(i1)putchar( );
164 printf(%d,ans[i]summ);
165 }
166 puts();
167 }
168 return 0;
169 } 转载于:https://www.cnblogs.com/xseventh/p/9986194.html
