結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2023-01-10 19:10:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 230 ms / 3,000 ms |
コード長 | 4,929 bytes |
コンパイル時間 | 3,042 ms |
コンパイル使用メモリ | 209,824 KB |
最終ジャッジ日時 | 2025-02-10 01:34:51 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define ALL(x) begin(x),end(x)#define rep(i,n) for(int i=0;i<(n);i++)#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define mod 1000000007using ll=long long;const int INF=1000000000;const ll LINF=1001002003004005006ll;int dx[]={1,0,-1,0},dy[]={0,1,0,-1};// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}struct IOSetup{IOSetup(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(12);}} iosetup;template<typename T>ostream &operator<<(ostream &os,const vector<T>&v){for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");return os;}template<typename T>istream &operator>>(istream &is,vector<T>&v){for(T &x:v)is>>x;return is;}#line 1 "Graph2/GraphTemplate.cpp"// graph template// ref : https://ei1333.github.io/library/graph/graph-template.cpptemplate<typename T=int>struct Edge{int from,to;T w;int idx;Edge()=default;Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){}operator int() const{return to;}};template<typename T=int>struct Graph{vector<vector<Edge<T>>> g;int V,E;Graph()=default;Graph(int n):g(n),V(n),E(0){}int size(){return (int)g.size();}void resize(int k){g.resize(k);V=k;}inline const vector<Edge<T>> &operator[](int k)const{return (g.at(k));}inline vector<Edge<T>> &operator[](int k){return (g.at(k));}void add_directed_edge(int from,int to,T cost=1){g[from].emplace_back(from,to,cost,E++);}void add_edge(int from,int to,T cost=1){g[from].emplace_back(from,to,cost,E);g[to].emplace_back(to,from,cost,E++);}void read(int m,int pad=-1,bool weighted=false,bool directed=false){for(int i=0;i<m;i++){int u,v;cin>>u>>v;u+=pad,v+=pad;T w=T(1);if(weighted) cin>>w;if(directed) add_directed_edge(u,v,w);else add_edge(u,v,w);}}};#line 2 "Graph2/Rerooting.cpp"template<typename T,typename GT=int>struct Rerooting{using E=function<T(T,Edge<GT>)>;//集合,頂点番号using M=function<T(T,T)>;using F=function<T(T,int)>;Graph<GT> g;// dp_v = fix(merge(f(dp_c1,edge(v,c1)),...,f(dp_ck,edge(v,ck))),v)E f; // f(T,Edge)->T 辺情報を考慮し,merge前の形M merge;// TxT->T,子を集約する関数,モノイドT e; // mergeの単位元F fix; // TxN->T 補正vector<vector<T>> dp;vector<T> ans;Rerooting(Graph<GT> &g,E f,M merge,T e,F fix=[](T a,int b){return a;}):g(g),f(f),merge(merge),e(e),fix(fix),dp(g.size()),ans(g.size(),e){}T dfs1(int pre,int now){T ret=e;for(int i=0;i<(int)g[now].size();i++)if(g[now][i]!=pre){dp[now][i]=dfs1(now,g[now][i]);ret=merge(ret,f(dp[now][i],g[now][i]));}return fix(ret,now);}void dfs2(int pre,int now,T frompar){for(int i=0;i<(int)g[now].size();i++){if(g[now][i]==pre){dp[now][i]=frompar;break;}}vector<T> lsum(g[now].size()+1),rsum(g[now].size()+1);//親も混ぜて累積lsum[0]=e;rsum[g[now].size()]=e;for(int i=0;i<(int)g[now].size();i++) lsum[i+1]=merge(lsum[i],f(dp[now][i],g[now][i]));for(int i=(int)g[now].size();i>0;i--) rsum[i-1]=merge(rsum[i],f(dp[now][i-1],g[now][i-1]));for(int i=0;i<(int)g[now].size();i++)if(g[now][i]!=pre){T fromme=merge(lsum[i],rsum[i+1]);dfs2(now,g[now][i],fix(fromme,now));}}void build(int root=0){for(int i=0;i<(int)g.size();i++) dp[i].resize(g[i].size());dfs1(-1,root);dfs2(-1,root,e);for(int i=0;i<(int)g.size();i++){for(int j=0;j<(int)g[i].size();j++) ans[i]=merge(ans[i],f(dp[i][j],g[i][j]));ans[i]=fix(ans[i],i);}}};signed main(){int N; cin >> N;Graph<int> G(N);rep(i, N - 1){int u, v; cin >> u >> v;u--, v--;G.add_edge(u, v);}vector<int> start(N, 0);start[0] = 1;for(int i = 1; i < N; i++){if(G[i].size() == 1) start[i] = 1;}auto fix = [&](int val, int cur){if(start[cur]) return 0;else return 1 + val;};auto merge = [&](int l, int r){return min(l, r);};auto f = [&](int val, Edge<int> e){return val;};Rerooting<int> R(G, f, merge, INF, fix);R.build();rep(i, N) cout << R.ans[i] << "\n";return 0;}