oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1696 看來我對重心剖分的理解還不夠QQ，一直想成重心樹的父子關係會跟原本的樹一樣。 我對於每個重心樹上的點維護他重心子樹們中$ dis \leq i, \forall 0 \leq i \leq D_{max} $的人有幾個(其中dis代表在原樹上的距離)，以及扣掉某個小孩的子樹後的這坨值。接著對於每個人就當做一個詢問，從葉子往上走訪重心樹，同時查詢不走剛剛來的那個點的子樹，距離好的點有幾個。 #include <bits/stdc++.h> using namespace std; #define ALL(x) begin(x), end(x) #define PB push_back #define SZ(x) ((int)(x).size()) const int N = 100000 + 5; struct node{ int cur, dis; node(int a=-1,int b=0):cur(a),dis(b){} }; vector<node> path[N]; vector<int> sum[N], fa_sum[N]; bool done[N]; int sz[N], M[N], fa[N], dis[N], que[N], cen[N]; vector<int> G[N]; int CenDe(int); int Query(int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin >> n; for(int i=1;i<=n;i++) cin >> que[i]; for(int i=0;i<n-1;i++){ int u, v; cin >> u >> v; G[u].PB(...

題目連結: http://tioj.infor.org/problems/1214 前面 稍微講了一下用hash的作法，不過當參數取的不好時，hash是很有可能會撞的。如果一定要確定性的算法的話，可以把hash作法改成:對於葉節點先定義一個值，而對於非葉節點則蒐集起他所有子樹的hash值排序好後塞到map之類的容器並訂一個值(例如直接用map的size)，那這樣複雜度會退化成$O(nlogn)$但是就不會有碰撞的問題了。 1214. 樹論 之 樹同構測試 4 1272 Accepted 100 Testdata no. Time (ms) Memory (KiB) Verdict 0 4 1272 Accepted Submitter: ototot Compiler: c++11 Code Length: 1.77 KB #include <bits/stdc++.h> using namespace std; #define FF first #define SS second #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100 + 5; vector<int> G1[N], G2[N]; int sz1[N], sz2[N]; map<vector<int>,int> bkt; inline void init(int); int GetCentroid(vector<int>[],int[],int,int,int); int Hash(vector<int>[],int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>...

題目連結: http://tioj.infor.org/problems/1214 原本以為可以拿個中序前序之類的來判，但感覺還是慘慘的。後來才知道原來其實可以把一整棵樹的形狀hash起來，這樣的話就可以直接看hash值來判了，不過要怎麼hash呢?這裡的作法是先定義葉節點的hash值，而其他非葉節點則將他所有子樹的hash值平方後加起來，這樣只要根一樣的話那hash出來的值就會一樣(但有可能有碰撞)，但是這題給的是棵無根樹，若沒有用一些好方法定根，那hash出來的值就很有可能不一樣，這裡利用樹的一個特殊的性質－一顆樹的重心最多只有兩顆，所以用重心當根判一下就可以有$O(n)$的複雜度了。 #include <bits/stdc++.h> using namespace std; typedef unsigned long long llu; #define FF first #define SS second #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100 + 5; const int mod = 44478311; vector<int> G1[N], G2[N]; int sz1[N], sz2[N]; inline void init(int); int GetCentroid(vector<int>[],int[],int,int,int); llu Hash(vector<int>[],int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n, n){ init(n); for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; ...

題目連結: http://tioj.infor.org/problems/1947 裸樹重心題，而要怎麼找樹重心呢?直接DFS吧，在DFS時你就知道他小孩的子樹大小，而他祖先那塊子樹不難發現就是點數減下子樹的數量，然後就記個最小值大概這樣吧 #include <cstdio> #include <vector> #include <algorithm> typedef long long lld; using std::max; using std::min; using std::vector; lld n,m=2147483647999; vector<int> graph[1000010]; inline lld DFS(int,int); int main(){ scanf("%d",&n); for(int i=0;i<n-1;i++){ int a,b; scanf("%d%d",&a,&b); graph[a].push_back(b); graph[b].push_back(a); } DFS(0,-1); printf("%lld",m); return 0; } inline lld DFS(int k,int f){ lld size=1; lld sub=0; for(int i=0;i<graph[k].size();i++){ if(graph[k][i] == f)continue; lld each=DFS(graph[k][i],k); sub=max(each, sub); size+=each; } ...