結果
問題 | No.2618 除霊 |
ユーザー |
|
提出日時 | 2024-01-26 21:57:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 1,653 bytes |
コンパイル時間 | 1,805 ms |
コンパイル使用メモリ | 171,008 KB |
実行使用メモリ | 45,440 KB |
最終ジャッジ日時 | 2024-09-28 08:07:32 |
合計ジャッジ時間 | 13,256 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 43 |
ソースコード
// Problem: No.2618 除霊// Contest: yukicoder// URL: https://yukicoder.me/problems/no/2618// Memory Limit: 512 MB// Time Limit: 2000 ms#include<bits/stdc++.h>#define debug(x) cerr<<(#x)<<" "<<(x)<<endltypedef long long ll;typedef long double ld;typedef unsigned long long ull;#define pii pair<ll,ll>#define rep(i,a,b) for(ll i=(a);i<=(b);++i)#define per(i,a,b) for(ll i=(a);i>=(b);--i)using namespace std;bool Mbe;ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}void write(ll x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}const ll N=5e5+9;ll n,m,a[N],po[N],sum[N],tr[N],tag[N],ent[N],fa[N];vector<ll>to[N];void dfs(ll x,ll f){fa[x]=f;for(ll y:to[x]){if(y==f)continue;dfs(y,x);sum[x]+=tr[y];tr[x]+=tr[y];if(!ent[y]&&!tag[y]&&tag[x])tr[x]++;ent[x]+=tag[y];}tr[x]+=(ent[x]||tag[x]);}bool Med;int main(){cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";n=read();rep(i,2,n){ll x=read(),y=read();to[x].push_back(y);to[y].push_back(x);}m=read();rep(i,1,m)a[i]=read(),tag[a[i]]=1;rep(i,1,m){po[a[i]]++;for(ll j:to[a[i]])po[j]++;}dfs(1,0);rep(i,1,n){ll res=tr[1]-(i==1?tr[1]:tr[fa[i]]);if(po[fa[i]]&&ent[fa[i]]+tag[fa[i]]==0)res--;if(fa[fa[i]]){ll c=po[fa[fa[i]]]-tag[fa[i]];if(!c&&po[fa[fa[i]]])res--;}for(ll j:to[i]){if(j==fa[i])continue;res+=sum[j]+(po[j]-tag[i]-tag[j]?1:0);}ll j=fa[i];if(j){res+=sum[j]-tr[i];if(po[j]-tag[i]-tag[j])res++;}write(res),putchar('\n');}return 0;}